djikstra

#include <stdio.h>
#include <algorithm>
#include <vector>
#include<queue>
#include<limits.h>
#include<functional>
using namespace std;
FILE *in = stdin;
FILE *out = stdout;
typedef pair<int, int> pii;
int n, m;
vector <pii> v[100005];
long long dis[100005];
int p[100005];
int ans[100005];
int main() {
    fscanf(in, "%d %d", &n, &m);
    for (int i = 1; i <= n; i++) {
        dis[i] = LLONG_MAX;
    }
    for (int i = 1; i <= m; i++) {
        int x, y, z;
        fscanf(in, "%d %d %d", &x, &y, &z);
        v[x].push_back(make_pair(z, y));
        v[y].push_back(make_pair(z, x));
    }
    dis[1] = 0;
    priority_queue<pair<long long, int>, vector<pair<long long, int> >, greater<pair<long long, int> >> pq;
    pq.push(make_pair(0, 1));
    while (!pq.empty()) {
        int pos = pq.top().second;
        pq.pop();
        for (int i = 0; i < v[pos].size(); i++) {
            if (v[pos][i].first + dis[pos] < dis[v[pos][i].second]) {
                pq.push(make_pair(v[pos][i].first + dis[pos], v[pos][i].second));
                dis[v[pos][i].second] = v[pos][i].first + dis[pos];
                p[v[pos][i].second] = pos;
            }
        }
    }
    int now = n;
    int dude = 1;
    int check = 1;
    bool bro = false;
    while (now != 1) {
        ans[dude] = now;
        dude++;
        now = p[now];
        if (check > n) {
            bro = true;
            break;
        }
        check++;
    }
    if (bro) fprintf(out, "-1");
    else {
        fprintf(out, "1 ");
        for (int i = dude - 1; i >= 1; i--) {
            fprintf(out, "%d ", ans[i]);
        }
    }
    return 0;
}