dijkstra.cpp

#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define pb push_back
#define INF 0x7fffffff
#define sz 100005
priority_queue<pii,vector<pii>,greater<pii> >q;
vector<pii>G[sz];
int dist[sz];
bool vis[sz];
int parent[sz];
int n,m;
void printpath(int src)
{
    if(parent[src]!=-1)
        printpath(parent[src]);
    cout<<src<<" ";
}
void dijktras(int src)
{
    for(int i=0; i<=n; i++)
    {
        dist[i]=INF;
        vis[i]=false;
        parent[i]=-1;
    }
    dist[src]=0;
    q.push(pii(0,src));
    while(!q.empty())
    {
        int s=q.top().second;
        q.pop();
        for(int i=0; i<G[s].size(); i++)
        {
            int v=G[s][i].second;
            int w=G[s][i].first;
            if(!vis[v] && dist[s]+w<dist[v])
            {
                dist[v]=dist[s]+w;
                q.push(pii(dist[v],v));
                parent[v]=s;
            }
        }
        vis[s]=true;
    }
}
int main()
{

    cin>>n>>m;
    while(m--)
    {
        int a,b,w;
        cin>>a>>b>>w;
        G[a].pb(pii(w,b));
        G[b].pb(pii(w,a));
    }
    dijktras(1);
    if(dist[n]==INF)
    {
        cout<<"-1"<<endl;
    }
    else
        printpath(n);
    return 0;
}