Given an undirected weighted connected graph, it is required to 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.
While creating the Really Special SubTree, start by picking the edge with smallest weight. If there are edges of equal weight available at an instant, then the edge to be chosen first among them is the one with minimum value of sum of the following expression :
u + wt + v , where u and v are the node numbers of the corresponding edge and wt is the weight.
Even then if there is a collision, choose any one of them.
While doing the above, ensure that no cycle is formed while picking up edges.
Finally, you need to print the overall weight of the Tree so formed using above rules.
First line has two integers , denoting the number of nodes in the graph and , denoting the number of 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, denotes the weight of edge between the corresponding nodes.
*Note: * If there are edges between the same pair of nodes with different weights, they are to be considered as is, like multiple edges.
Print a single integer denoting the total weight (sum of weights of all edges in the MST) of the Really Special SubTree.
Sample Input 0
4 61 2 51 3 34 1 62 4 73 2 43 4 5
Sample Output 0
The graph given in the test case is shown as :
The nodes A,B,C and D denote the obvious 1,2,3 and 4 node numbers.
The starting node is A or 1 (in the given test case)
Applying the Kruskal's algorithm, all the edges are sorted in ascending order of weight.
After sorting, the edge choices are available as :