Consider a undirected graph, G(N,A), where N and A are the set of nodes and arcs (edges), respectively. Associated with each arc (i,j) in A is a cost c(i,j). Let |N| = n and |A|=m. The problem is to find a rooted undirected spanning tree, G(N,S) where S is a subset of A such that the sum of c(i,j) for all (i,j) in S is minimized. The rooted undirected spanning tree is defined as a graph which connects, without any cycle, all nodes with n-1 arcs, i.e., each node, except the root, has one and only one incoming arc.

You are required to read a graph from a text file. The first 2 numbers (N and E) in the text file specifies the number of vertices and the number of edges available. Follows are the E lines each specifying a link between 2 nodes.

The problem is to find a minimum spanning tree.

Sample input:

8 10

0 1 9

1 3 7

2 3 15

3 4 10

4 6 8

4 5 3

5 6 14

1 6 5

6 7 6

1 7 12

Sample output (The sum of the weights of the spanning tree edges)

53