1
#include <vector>
2
#include <iostream>
3
#include <map>
4
#include <algorithm>
5
#include <queue>
6
#include <set>
7
 
8
using namespace std;
9
 
10
 
11
 
12
int main() {
13
    int n, m;
14
    cin >> n >> m;
15
    vector<pair<int, int>> g[n];
16
 
17
    for (int i = 0; i < m; i++ ){
18
        int v, u, w;
19
        cin >> v >> u >> w;
20
        v--; u--;
21
        g[v].push_back({u, w});
22
        g[u].push_back({v, w});
23
    }
24
 
25
    vector<int> d(n, INT_MAX);
26
    d[0] = 0;
27
 
28
    set<pair<int, int>> s;
29
    for (int i = 0; i < n; i++) {
30
        s.insert({d[i], i});
31
    }
32
 
33
    for (int i = 0; i < n; i++) {
34
        pair<int, int> s_begin = *s.begin();
35
        int v = s_begin.second;
36
 
37
        s.erase(s_begin);
38
 
39
        for (int j = 0; j < g[v].size(); j++) {
40
            int to = g[v][j].first;
41
            int w = g[v][j].second;
42
 
43
            if (d[v] + w < d[to]) {
44
                s.erase({d[to], to});
45
                s.insert({d[v] + w, to});
46
                d[to] = d[v] + w;
47
            }
48
        }
49
    }
50
    // O(n^2 + m)
51
    // O(n + m log n)
52
    // if m = n^2: первое лучше
53
 
54
    for (int i = 0; i < n; i++) {
55
        cout << d[i] << " ";
56
    }
57
}