Given a graph with N nodes and M edges (**Undirected**) with positive weights. Find the minimum spanning tree. A **tree** with **minimum overall weight** edge. This is cover all nodes of the original graph if possible. You will be given a starting point S. Just in case the graph is not connected. Then you can find the MST which contains S.

**Input Format**

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 , first two integers are the two nodes between which the edge exists, last/third integer is the weight of the edge.

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

Nodes are numbered from 1 to N.

There can be multiple edges between same pair of nodes. Consider them as multiple edges.

Sample input:

```
3 3
1 2 2
1 3 3
3 2 6
1
```

**Sample Output**

5

**Solution:**

</pre> #include <cmath> #include <cstdio> #include <vector> #include <iostream> #include <algorithm> using namespace std; struct edge{ int begin; int end; int weight; }; //minHeap bool comp(const edge& a, const edge& b){ return (a.weight > b.weight); } void print(edge e){ cout<<e.begin<<" -> "<<e.end<<" w: "<<e.weight<<endl; } void prims(vector <vector <edge> > &adj, int start, int V){ vector <edge> minHeap; int result = 0; for(int i = 0; i < adj[start].size(); i++){ minHeap.push_back(adj[start][i]); //print(adj[start][i]); } make_heap (minHeap.begin(),minHeap.end(), comp); vector <bool> visited(V); visited[start] = true; while(!minHeap.empty()){ edge e = minHeap.front(); //cout<<"popped "; //print(e); pop_heap(minHeap.begin(), minHeap.end(),comp); minHeap.pop_back(); if(!visited[e.end]){ visited[e.end] = true; result += e.weight; //cout<<"res: "<<result<<endl; for(int i = 0; i < adj[e.end].size(); i++){ minHeap.push_back(adj[e.end][i]); push_heap(minHeap.begin(), minHeap.end(), comp); //cout<<"push "; //print(adj[e.end][i]); } } } cout<<result<<endl; } int main() { int V, E, S; cin>>V; cin>>E; vector <vector <edge> > adj(V); for(int i = 0; i < E; i++){ int start, end, weight; cin>>start; cin>>end; cin>>weight; start--;end--; edge e1; e1.end = end; e1.weight = weight; e1.begin = start; adj[start].push_back(e1); edge e2; e2.end = start; e2.weight = weight; e2.begin = end; adj[end].push_back(e2); } cin>>S; S--; prims(adj,S, V); /* Enter your code here. Read input from STDIN. Print output to STDOUT */ return 0; }