Dijkstra

#include <utility>
#define pb push_back
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>


using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    long long dist[100005];
    long long path[100005];

    for (long long i=0; i < 100005; i++) {
        dist[i] = 900190019001;
    }

    dist[1] = 0;

    vector<pair<long long, long long> > g[100005];

    long long n, m;
    cin >> n >> m;
    for (long long i=0; i < m; i++) {
        long long a, b, w;
        cin >> a >> b >> w;
        g[a].pb(pair<long long, long long>(b, w));
        g[b].pb(pair<long long, long long>(a, w));
    }

    priority_queue< pair<long long, long long>, vector<pair<long long, long long> >, greater<pair<long long, long long> > > pq;
    pq.push(pair<long long, long long>(0, 1));

    while (!pq.empty()) {

        pair<long long, long long> front = pq.top();
        pq.pop();
        long long d = front.first;
        long long u = front.second;
        if (d > dist[u]) {
            continue;
        }

        for (long long j=0; j < g[u].size(); j++) {
            pair<long long, long long> v = g[u][j];
            if (dist[u] + v.second < dist[v.first]) {
                dist[v.first] = dist[u] + v.second;
                pq.push(pair<long long, long long>(dist[v.first], v.first));
                path[v.first] = u;
            }
        }
    }

    if (dist[n] == 900190019001) {
        cout << -1 << endl;
        return 0;
    }

    vector<long long> x;
    long long i = n;
    while (i != 1) {
        x.pb(i);
        i = path[i];
    }
    x.pb(1);

    for (long long i = x.size()-1; i >= 0; i--) {
        cout << x[i] << " ";
    }
    return 0;
}