1
#include <bits/stdc++.h>
2

3
#define N 5010
4
#define M 5010
5
using namespace std;
6

7
struct Edge {
8
    int to, ne, w;
9
} edges[M];
10
int h[N], idx = 0;
11
int n, m;
12
int dist[N], cnt[N];
13
bool st[N];
14

15
void add(int u, int v, int w) {
16
    idx++;
17
    edges[idx].to = v;
18
    edges[idx].ne = h[u];
19
    edges[idx].w = w;
20
    h[u] = idx;
21
}
22

23
bool spfa() {
24
    memset(dist, 0x3f, sizeof dist);
25

26
    queue<int> q;
27
    for(int i = 1; i <= n; i++) {
28
        q.push(i);
29
        st[i] = true;
30
        dist[i] = 0;
31
    }
32

33
    while (!q.empty()) {
34
        int t = q.front();
35
        q.pop();
36

37
        st[t] = false;
38
        for (int i = h[t]; ~i; i = edges[i].ne) {
39
            int j = edges[i].to;
40
            if (dist[j] > dist[t] + edges[i].w) {
41
                dist[j] = dist[t] + edges[i].w;
42
                cnt[j] = cnt[t] + 1;
43
                if (cnt[j] >= n) return false;
44
                if (!st[j]) {
45
                    st[j] = true;
46
                    q.push(j);
47
                }
48
            }
49
        }
50
    }
51
    return true;
52
}
53

54
int main() {
55
    ios::sync_with_stdio(false);
56
    cin.tie(nullptr);
57
    cout.tie(nullptr);
58

59
    memset(h, -1, sizeof h);
60

61
    cin >> n >> m;
62
    while (m--) {
63
        int u, v, w;
64
        cin >> v >> u >> w;
65
        add(u, v, w);
66
    }
67
    if (!spfa()) cout << "NO" << endl;
68
    else {
69
        for (int i = 1; i <= n; i++) cout << dist[i] << ' ';
70
    }
71
    return 0;
72
}