Given an undirected weighted connected graph, find the Really Special SubTree in it. The Really Special SubTree is defined as a subgraph consisting of all the nodes in the graph and:
- There is only one exclusive path from a node to every other node.
- The subgraph is of minimum overall weight (sum of all edges) among all such subgraphs.
- No cycles are formed
To create the Really Special SubTree, always pick the edge with smallest weight. Determine if including it will create a cycle. If so, ignore the edge. If there are edges of equal weight available:
- Choose the edge that minimizes the sum where and are vertices and is the edge weight.
- If there is still a collision, choose any of them.
Print the overall weight of the tree formed using the rules.
For example, given the following edges:
u v wt
1 2 2
2 3 3
3 1 5
First we would choose at weight . Next we would choose at weight . All nodes are connected without cycles for a total weight of .
Input Format
The first line has two integers and , the number of nodes and edges in the graph.
The next lines each consist of three space separated integers , , where and denote the two nodes between which the undirected edge exists and denotes the weight of that edge.
Constraints
**Note: ** If there are edges between the same pair of nodes with different weights, they are to be considered as is, like multiple edges.
Output Format
Print a single integer denoting the total weight of the Really Special SubTree.
Sample Input 1
4 6
1 2 5
1 3 3
4 1 6
2 4 7
3 2 4
3 4 5
Sample Output 1
12
Explanation 1
The graph given in the test case is shown as :
The nodes A,B,C and D denote the 1,2,3 and 4 node numbers.
The starting node is A or 1 in the given test case.
Applying Kruskal's algorithm, all the edges are sorted in ascending order of weight.
After sorting, the edge choices are available as :
A->C (WT. 3) , B->C (WT. 4) , A->B (WT. 5) , C->D (WT. 5) , A->D (WT. 6) and B->D (WT. 7)
Picking these edges and finalizing only if it doesnt create a cycle :
A->C : B->C
The edge A->B would form a cycle so it is ignored.
The edge C->D is chosen to finish the MST:
A->C : B->C : C->D
The total weight of the Really Special SubTree is : 12