class Solution
{
	public:
	//Function to find sum of weights of edges of the Minimum Spanning Tree.
    int spanningTree(int V, vector<vector<int>> adj[])
    {
        // code here
        vector<int> vis(V,0);
        vector<tuple<int,int,int>> mst;
        //wt,node,parent
        priority_queue<vector<int>,vector<vector<int>>, greater<vector<int>>> pq;
        
        pq.push({0,0,-1});
        int sum =0;
        
        while(!pq.empty()){
            auto it = pq.top();
            pq.pop();
            int node = it[1];
            int wt = it[0];
            int par = it[2];
            
            if(vis[node]==1) continue;
            vis[node]=1;
            sum+=wt;
            if(par!=-1){
                mst.push_back(make_tuple(wt,par,node));
            }
            for(auto it: adj[node]){
                int ch = it[0];
                int ch_w = it[1];
                if(!vis[ch]){
                    pq.push({ch_w, ch,node});
                }
            }
        }
        for(auto it: mst){
            int weight, u, v;
            tie(weight, u, v) = it;
            cout<<weight<<":"<<u<<"->"<<v<<endl;
        }
        return sum;
    }
};