Given a weighted, undirected, and connected graph. The task is to find the sum of weights of the edges of the Minimum Spanning Tree.

The task is to find the sum of weights of the edges of the Minimum Spanning Tree.

Input:
2
3 3
1 2 5 2 3 3 1 3 1
2 1
1 2 5
Output:
4
5
Example:
Testcase 1:  Sum of weights of edges in the minimum spanning tree is 4.

// { Driver Code Starts
#include <bits/stdc++.h>
using namespace std;
int spanningTree(int V, int E, vector<vector<int>> &graph);
// Driver code

int main() {
    int t;
    cin >> t;
    while (t--) {
        int V, E;
        cin >> V >> E;
        vector<vector<int> > graph(V, vector<int>(V, INT_MAX));

        while (E--) {
            int u, v, w;
            cin >> u >> v >> w;
            u--, v--;
            graph[u][v] = w;
            graph[v][u] = w;
        }

        cout << spanningTree(V, E, graph) << endl;
    }
    return 0;
}
// } Driver Code Ends


// Function to construct and print MST for
// a graph represented using adjacency
// matrix representation, with V vertices.
// graph[i][j] = weight if edge exits else INT_MAX
int spanningTree(int V, int E, vector< vector<int> > &graph ){

vector<int> key(V,INT_MAX);
vector<bool> vis(V,false);
key[0]=0;
int sum=0;
        for(int j=0;j<V;++j)
        {
           
           pair <int,int> p ;
           p.second=INT_MAX;
           
           for(int i=0;i<V;++i)
           {
                if(!vis[i]&&key[i]<p.second)
                {
                    p.second=key[i];
                    p.first=i;
                }
            
           }
           
            vis[p.first]=true;
            sum+=p.second;
            
            for(int i=0;i<V;++i)
            {
            if(!vis[i] && graph[p.first][i]!=INT_MAX && graph[p.first][i]<key[i])
                key[i]=graph[p.first][i];
            }
       
        }
    return sum;
}