Minimum Snow Clearing for Road Network

You are given a network of cities connected by roads. Each road is described by three integers (u), (v), and (w) where (u) and (v) represent cities and (w) represents the cost (or amount of snow) that needs to be cleared on that road. Your task is to clear a subset of roads such that all cities are connected and the total clearing cost is minimized, i.e. the cleared roads form a Minimum Spanning Tree (MST) of the network. In other words, you must compute the sum of the weights in the MST. Recall the MST is defined as a subgraph that connects all the vertices with the minimum possible total edge weight.

The input guarantees that the graph is connected.

inputFormat

The first line of the input contains two integers (n) and (m) where (n) is the number of cities and (m) is the number of roads. It is followed by (m) lines each containing three integers (u), (v) and (w). Here, (u) and (v) denote the connected cities (1-indexed) and (w) is the cost to clear the corresponding road. All input is provided via standard input (stdin).

outputFormat

Output a single integer representing the minimum total snow clearing cost required to form a spanning tree (i.e. the sum of weights in the MST) via standard output (stdout).## sample

4 3
1 2 5
2 3 1
2 4 3

9