some algos

//АЛГОРИТМ ДЕЙКСТРЫ оптимальный
const ll inf = 10000000000000ll;

int main()
{
    //freopen("input.txt", "r", stdin);
    //freopen("rvq.out", "w", stdout);
    cin.tie(NULL);
    cout.tie(NULL);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(10);

    int n, m, a, b, w;
    cin >> n >> m;
    vector<vector<pair<int, int>>> edges(n);
    vector<ll> dist(n, inf);
    vector<int> prev(n);


    int start = 0;
    int ender = n - 1;
    dist[start] = 0;

    for (int i = 0; i < m; i++) {
        cin >> a >> b >> w;
        a--, b--;
        edges[a].push_back({ b, w });
        edges[b].push_back({ a, w });
    }
    set<pair<ll, int> > s;
    s.insert({ dist[start], start });
    while (s.size() > 0) {
        int v = s.begin()->second;
        s.erase(s.begin());

        for (int i = 0; i < (int(edges[v].size())); ++i) {
            int prvi = edges[v][i].first;
            int w = edges[v][i].second;

            if (dist[v] + w < dist[prvi]) {
                s.erase({ dist[prvi], prvi });
                dist[prvi] = dist[v] + w;
                prev[prvi] = v;
                s.insert({ dist[prvi], prvi });
            }
        }
    }
    vector<int> way;
    if (dist[ender] == inf)
        cout << -1;
    else {
        int c = ender;
        while (c != start) {
            way.push_back(c);
            c = prev[c];
        }

        way.push_back(start);
        for (int i = (way.size()) - 1; i >= 0; --i)
            cout << (way[i]+1) << ' ';
    }

    return 0;
}






СНМ(система непересекающихся множеств):
//parent от 0 до n заполнить числами соответственно индексу 0...n
void make_set (int v) {
    parent[v] = v;
    rank[v] = 0;
}

int find_set (int v) {
    if (v == parent[v])
        return v;
    return parent[v] = find_set (parent[v]);
}

void union_sets (int a, int b) {
    a = find_set (a);
    b = find_set (b);
    if (a != b) {
        if (rank[a] < rank[b])
            swap (a, b);
        parent[b] = a;
        if (rank[a] == rank[b])
            ++rank[a];
    }
}


//функция Эйлера(кол-во взаимнопростых с n чисел от 0 до n-1)
int phi(int n){
    int res = n;

    for (int i = 2; i * i <= n; ++i){
        if (!(n % i)){
            while(!(n % i)){
                n /= i;
            }
            res -= res/ i;
        }
    }

    if (n > 1)
        res -= res / n;

    return res;
}


//z-функция - z[i] - наибольшее число символов, начиная с позиции i,
//совпадающих с первыми символами строки s.
vector<int> z_function (string s) {
    int n = (int) s.length();
    vector<int> z (n);
    for (int i=1, l=0, r=0; i<n; ++i) {
        if (i <= r)
            z[i] = min (r-i+1, z[i-l]);
        while (i+z[i] < n && s[z[i]] == s[i+z[i]])
            ++z[i];
        if (i+z[i]-1 > r)
            l = i,  r = i+z[i]-1;
    }
    return z;
}

//префикс функция - p[i] - длина наибольшего собственного суффикса подстроки s[0..i],
//совпадающего с её префиксом
vector<int> prefix_function(string s) {
    int n = (int)s.length();
    vector<int> pi(n);
    for (int i = 1; i < n; i++) {
        int j = pi[i-1];
        while (j > 0 && s[i] != s[j])
            j = pi[j-1];
        if (s[i] == s[j])
            j++;
        pi[i] = j;
    }
    return pi;
}

//Дерево Фенвика(почти как Дерево Отрезков)
T a[size];
/* precondition: pos > 0 */
void add(int pos, const T& val) {
    while (pos < size) {
        a[pos] += val;
        pos += pos & -pos;
    }
}
T sum(int pos) {
    T ret = T();
    while (pos > 0) {
        ret += a[pos];
        pos -= pos & -pos;
    }
    return ret;
}