Dijkstra

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

typedef pair<ll ,ll> ii;
#define S second
#define F first
#define OO 1e18

vector< vector< ii > > AdjList;
int n ,m;

void printPath( vector< ll > Parent ,int u){
    if( Parent[u] != u )
        printPath( Parent , Parent[u] );

    cout << u << ' ';
}

int main() {
    cin >> n >> m;
    AdjList.resize(n + 1);

    for(int i=0 ; i<m ; i++){
        int u ,v ,w; cin >> u >> v >> w;
        AdjList[u].push_back( {v,w} );
        AdjList[v].push_back( {u,w} );
    }

/// --- \Dijkstra --- ///
    priority_queue< ii , vector< ii > ,greater< ii > > pq;
    vector< ll > Dist(n + 1 ,OO) ,Parent(n + 1);

    // parents array : assign to each node => itself
    for(int i = 1 ; i <= n ; i++) Parent[i] = i;

    Dist[1] = 0;
    pq.push( {0 ,1} );
    while( !pq.empty() ){
        ii front = pq.top(); pq.pop();
        int u = front.S;
        ll  d = front.F;

        if( d > Dist[u] ) continue;

        for(int j = 0 ; j < (int)AdjList[u].size() ; j++) {
            ii v = AdjList[u][j];
            if( Dist[u] + v.S < Dist[ v.F ] ) {
                    // Set the parent of the v.F is u = to use it in the path print
                    Parent[ v.F ] = u;
                    Dist[ v.F ] = Dist[ u ] + v.S;
                    pq.push( ii( Dist[ v.F ] ,v.F ) );
            }
        }
    }

    if( Dist[n] == OO ) cout << -1 << endl;
    else printPath(Parent ,n);

    return 0;
}