sample sakim

#include<bits/stdc++.h>
using namespace std;
struct myself { int first, second; };
bool operator<(const myself &a, const myself &b) { return a.second > b.second; }
int main() {
    //freopen("input.txt", "r", stdin);
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int n, e; cin >> n >> e;
    vector<vector<myself>> adV(n + 1);
    unordered_map<int, bool> visited;
    for (int i = 1; i <= e; ++i) {
        int a, b, cost; cin >> a >> b >> cost;
        adV[a].push_back({ b,cost }); adV[b].push_back({ a, cost });
    }
    vector<int> parent(n + 1, 0), distTance(n + 1, INT32_MAX);
    bool flag = false;
    priority_queue<myself> s;
    s.push({ 1, 0 });
    while (!s.empty()) {
        myself p = s.top(); s.pop();
        int curNode = p.first, curCost = p.second;
        visited[curNode] = true;
        if (curNode == n) { flag = true; break; }
        for (auto des : adV[curNode]) {
            if (!visited[des.first]) {
                int totalCost = curCost + des.second;
                if (totalCost < distTance[des.first]) {
                    distTance[des.first] = totalCost;
                    s.push({ des.first, totalCost });
                    parent[des.first] = curNode;
                }
            }
        }
    }
    if (flag) {
        vector<int> ans; ans.push_back(n);
        int i = n;
        while (parent[i]) ans.push_back(parent[i]), i = parent[i];
        for (int i = ans.size() - 1; i >= 0; --i) cout << ans[i] << " ";
    }
    else cout << "-1";
    cout << "\n";
}