rt。

#include <cstring>
#include <iostream>
#define maxn 10100
using namespace std;
int head[maxn], nxt[maxn], to[maxn], w[maxn], cnt;
void add(int x, int y, int v) {
    nxt[++ cnt] = head[x]; head[x] = cnt; to[cnt] = y; w[cnt] = v;
}
int n, m, i, c1, c2, c3;
int dist[maxn], count[maxn], q[maxn], st, ed;
bool vis[maxn];
bool spfa(int s) {
    memset(dist, 0x3f, sizeof dist);
    dist[s] = 0, vis[s] = true;
    q[++ ed] = s;
    while (st <= ed) {
        int x = q[st ++], y;
        vis[x] = false;
        for (i = head[x]; i; i = nxt[i]) {
            y = to[i];
            if (dist[x] + w[i] < dist[y]) {
                dist[y] = dist[x]  + w[i];
                count[y] ++;
                if (count[y] > n) return false;
                if (!vis[y]) q[++ ed] = y, vis[y] = true;
            }
        }
    }
    return true;
}
int main() {
    cin >> n >> m;
    for (i = 1; i <= m; ++ i) {
        cin >> c1 >> c2 >> c3;
        add(c2, c1, c3);
    }
    for (i = 1; i <= n; ++ i) add(0, i, 0);
    if (!spfa(0)) return puts("NO"), 0;
    for (i = 1; i < n; ++ i) cout << dist[i] << ' ';
    cout << dist[n] << endl;
    return 0;
}