We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. 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.

Example


image

Starting from node , select the lower weight edge, i.e. , weight .

Choose between the remaining edges, , weight , and , weight .

The lower weight edge is weight .

All nodes are connected at a cost of . The edge is not included in the subgraph.

Function Description

Complete the prims function in the editor below.

prims has the following parameter(s):

  • int n: the number of nodes in the graph
  • int edges[m][3]: each element contains three integers, two nodes numbers that are connected and the weight of that edge
  • int start: the number of the starting node

Returns

  • int: the minimum weight to connect all nodes in the graph

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 , the starting node.

Constraints





There may be multiple edges between two nodes.

Sample Input

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

Sample Output

15

Explanation

The graph given in the test case is shown as :

Graph

  • 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 Total weight of the hence formed MST is : 15