Untitled

#include <bits/stdc++.h>

#define pb push_back
#define S second
#define F first
#define mp make_pair
#define pii pair<int,int>
#define ll long long

using namespace std;

const int N = 1e5 + 123;
const ll inf = 1e12 + 123;

int n, m;

ll d[N];

int p[N];

vector <pii> g[N];

set <pair <ll,int>> s;

int main () {
    ios_base::sync_with_stdio (0), cin.tie (0), cout.tie (0);
    cin >> n >> m;
    for (int i = 1;i <= m;i ++) {
        int l, r, x;
        cin >> l >> r >> x;
        g[l].pb (mp (r, x));
        g[r].pb (mp (l, x));
    }
    for (int i = 2;i <= n;i ++)d[i] = inf; 
    s.insert (mp (0, 1));
    while (!s.empty ()) {
        pii pr = *s.begin ();
        int v = pr.S;
        s.erase (s.begin ());
        for (auto it : g[v]) {
            int to = it.F;ll w = it.S;
            if (d[to] > d[v] + w) {
                s.erase (mp (d[to], to));
                d[to] = d[v] + w;
                s.insert (mp (d[to], to));
                p[to] = v;
            }
        }
    }
    if (d[n] == inf) {
        cout << -1;
        return 0;
    }
    vector <int> v;
    int id = n;
    while (id != 1) {
        v.pb (id);
        id = p[id];
    }
    v.pb (1);
    for (int i = v.size () - 1;i >= 0;i --) {
        cout << v[i] << ' ';
    }
}