Дейкстра

#include <iostream>
#include <set>
#include <vector>
#include <deque>
#include <map>
#include <cmath>
#include <random>

#define se second
#define fi first
#define mp make_pair
#define pb push_back

typedef long long ll;
typedef long double ld;

using namespace std;

const int inf = (int)1e9;

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<pair<int, int>>> g(n);
    for (int i = 0; i < m; i++) {
        int x, y, W;
        cin >> x >> y >> W;
        x--, y--;
        g[x].push_back(make_pair(y, W));
        g[y].push_back(make_pair(x, W));
    }
    int start;
    cin >> start;
    start--;
    vector<int> w(n, inf);
    w[start] = 0;
    set<pair<int, int>> st;
    for (int i = 0; i < n; i++) {
        st.insert({w[i], i});
    }
    while (!st.empty()) {
        pair<int, int> cur_pair = *st.begin();
        st.erase(cur_pair);
        int cur_rst = cur_pair.first;
        int cur = cur_pair.second;
        for (auto e : g[cur]) {
            int nxt = e.first;
            int cur_nxt_w = e.second;
            if (w[nxt] > w[cur] + cur_nxt_w) {
                st.erase({w[nxt], nxt});
                w[nxt] = w[cur] + cur_nxt_w;
                st.insert({w[nxt], nxt});
            }
        }
    }
    for (auto e : w) cout << e << ' ';
    return 0;
}