Dijkstra

vector <pair<int, int> > adj[MX];
priority_queue <pii, vector<pii >, greater<pii> > pq;

ll dist[MX];
int pa[MX];

void test_case() {
    int n, m;
    cin >> n >> m;
    while (m--) {
        int u, v, w;
        scanf("%d %d %d", &u, &v, &w);
        adj[u].pb({v, w});
        adj[v].pb({u, w});
    }
    for (int i = 1; i <= n; i++)
        dist[i] = inf;
    dist[1] = 0;
    pq.push({0, 1});
    while (!pq.empty()) {
        pair <ll, int> v = pq.top();
        pq.pop();
        if (v.F != dist[v.S]) continue;
        for (auto edge: adj[v.S]) {
            int to = edge.F, len = edge.S;
            if (dist[v.S] + len < dist[to]) {
                dist[to] = dist[v.S] + len;
                pa[to] = v.S;
                pq.push({dist[to], to});
            }
        }
    }
    if (dist[n] == inf) {
        cout << -1 << endl;
        return;
    }
    vector <int> res;
    while (n != 1) {
        res.pb(n);
        n = pa[n];
    }
    res.pb(1);
    reverse(res.begin(), res.end());
    for (auto u: res)
        printf("%d ", u);
    cout << "\n";
    return;
}