- Practice
- Algorithms
- Graph Theory
- Kruskal (MST): Really Special Subtree

# Kruskal (MST): Really Special Subtree

# Kruskal (MST): Really Special Subtree

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.

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**