5.Dijkstra's algorithm

 #include<bits/stdc++.h>

using namespace std;

int main()

{

 

      int n,m,i;

      cin>>n>>m;

      int vis[n+1];

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

      int dist[n+1];

      int parent[n+1];

      for(i=0;i<=n;i++)

      {

          dist[i]=1e8;

          parent[i]=i;

      }

      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});

      }

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

     dist[1]=0;

     pq.push({0,1});

     while (!pq.empty())

     {

          int node=pq.top().second;

          int durutto=pq.top().first;

          pq.pop();

          for(auto u:adj[node])

          {

             if((durutto+u.second)<dist[u.first])

             {

                  dist[u.first]=(durutto+u.second);

                  pq.push( {dist[u.first],u.first});

                  parent[u.first]=node;

             }

          }

      

     }

     for(i=0;i<=n;i++)

     {

         cout<<dist[i]<<" ";

     }

     cout<<endl;

     int node=6;

     while(node!=parent[node])

     {

         cout<<node<<" ";

         node=parent[node];

     }

     cout<<1<<endl;

    return 0;

}