- Practice
- Algorithms
- Graph Theory
- Prim's (MST) : Special Subtree

# Prim's (MST) : Special Subtree

Given a graph which consists of several edges connecting its nodes, find a subgraph of the given graph with the following properties:

- The subgraph contains all the nodes present in the original graph.
- The subgraph is of minimum overall weight (sum of all edges) among all such subgraphs.
- It is also required that there is
**exactly one, exclusive**path between any two nodes of the subgraph.

One specific node is fixed as the starting point of finding the subgraph using Prim's Algorithm.

Find the total weight or the sum of all edges in the subgraph.

For example, consider a graph with nodes. Edges are weight , weight and weight . Starting from , we select the lowest weight path, i.e. . From , there is only one path . We have all nodes connected at a cost of .

**Input Format**

The first line has two space-separated integers and , the number of nodes and edges in the graph.

Each of the next lines contains three space-separated integers , and , the end nodes of , and the edge's weight.

The last line has an integer , denoting the starting node.

**Constraints**

**There may be multiple edges between two nodes.**

**Output Format**

Print a single integer denoting the total weight of the subgraph.

**Sample Input 0**

```
5 6
1 2 3
1 3 4
4 2 6
5 2 2
2 3 5
3 5 7
1
```

**Sample Output 0**

```
15
```

**Explanation 0**

The graph given in the test case is shown as :

The nodes A,B,C,D and E denote the obvious 1,2,3,4 and 5 node numbers.

The starting node is A or 1 (in the given test case)

Applying the Prim's algorithm, edge choices available at first are :

A->B (**WT. 3**) and A->C (**WT. 4**) , out of which A->B is chosen (smaller weight of edge).

Now the available choices are :

A->C (**WT. 4**) , B->C (**WT. 5**) , B->E (**WT. 2**) and B->D (**WT. 6**) , out of which B->E is chosen by the algorithm.

Following the same method of the algorithm, the next chosen edges , sequentially are :

A->C and B->D.

Hence the overall sequence of edges picked up by prims are:

**A->B : B->E : A->C : B->D**

and the total weight of the MST (minimum spanning tree) is : **3+2+4+7=15**