Some error occured while loading page for you. Please try again.
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:
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:
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 .
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.
**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 of the Really Special SubTree.
Sample Input 1
Undirected Weighed Graph: g
4 61 2 51 3 34 1 62 4 73 2 43 4 5
Sample Output 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