Minimum Random Forest [In Python]

In this problem, you will be given a weighted disconnected undirected graph G with N nodes, labelled as 1...N and E edges. You will be required to find the weights of minimum spanning trees in Gs maximum random forest. A minimum spanning forest is a union of the minimum spanning trees for its connected components. Input Format The first line will contain a positive integer N. The second line will contain a positive integer E. Then E lines will follow each containing three space separated integers. The first two will denote the node labels which will be the end points of an undirected edge and the the third integer will be denoting the weight of that edge. Constraints 0 < N < 100 0 < E < N*(N - 1)/2 + 1 Output Format Each line of the output should contain a single integer denoting the weight of one of the minimum spanning trees.

The order doesnt matter and the weight of a particular minimum spanning tree should be printed only once.

Sample Input

6 6 1 2 2 2 3 2 3 1 1 4 5 2 5 6 2 6 4 1

Sample Output -

3

3

Explanation

The graph contains six nodes and six edges i.e., (1, 2), (2, 3), (3, 1) and (4, 5), (5, 6) and (6, 4). Since there are two connected components, (1, 2, 3) and (4, 5, 6) and each has a minimum spanning tree of weight 3. Hence, the above output is obtained.