SPFA: Dijkstra

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


using namespace std;
long long dist[100005];
long long path[100005];
queue<long long> q;
vector<long long> in_queue(100005, 0);
vector<pair<long long, long long> > g[100005];
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    in_queue[1] = 1;

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

    dist[1] = 0;


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

    q.push(1);

    while (!q.empty()) {
        long long u = q.front();
        q.pop();
        in_queue[u] = 0;
        for (long long j=0; j < g[u].size(); j++) {
            long long v = g[u][j].first;
            long long w = g[u][j].second;
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                if (!in_queue[v]) {
                    q.push(v);
                    in_queue[v] = 1;
                }
            }
        }
    }
    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;
}