5.prim's algorithm

 #include <bits/stdc++.h>

using namespace std;

int main()

{

    ios_base::sync_with_stdio(0);

    cin.tie(0);

    cout.tie(0);

   

     int n,m,i,j;

      cin>>n>>m;

      vector<pair<int,int>>adj[n+1];

      for(i=1;i<=m;i++)

      {

          int u,v,w;

          cin>>u>>v>>w;

          adj[u].push_back({v,w});

          adj[v].push_back({u,w});

      }

      int sum=0;

      int vis[n+1]={0};

      vector<pair<int,int>>ans;

      priority_queue<pair<int,pair<int,int>>,vector<pair<int,pair<int,int>>>,greater<pair<int,pair<int,int>>>>pq;

      int start_node;

      cin>>start_node;

      pq.push({0,{start_node,-1}});

      while(!pq.empty())

      {

          int node=pq.top().second.first;

          int parent=pq.top().second.second;

          int wt=pq.top().first;

          pq.pop();

          if(vis[node])continue;

          if(parent!=-1)

          {

               sum+=wt;

               ans.push_back({parent,node});

          }

          vis[node]=1;

       for(auto it:adj[node])

       {

           if(vis[it.first])continue;

           pq.push({it.second,{it.first,node}});

       }

      }

      cout<<"total sum : "<<sum<<endl;

      for(auto u:ans)

      {

         cout<<u.first<<"---"<<u.second<<endl;

      }

    return 0;

}