#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
const int N = 1e4+5,M =1e4+5,mod = 7;
ll n, m;
struct Edge {
    ll to, w;
};
vector<Edge> G[N];

ll dis[N], cnt[N];
bool vis[N];
bool spfa(ll s) {
    memset(dis, 127, sizeof(dis));
    dis[s] = 0;
    queue<ll> que;
    que.push(s);
    vis[s] = 1;
    while (que.size()) {
        s = que.front();
        que.pop();
        vis[s] = 0;
        for (Edge p :G[s]) {
            ll to = p.to, w = p.w;
            if (dis[to] > dis[s] +w) {
                dis[to] = dis[s] + w;
                cnt[to] = cnt[s] + 1;
                if (cnt[to]>=n+1)
                    return false;
                if (!vis[to]) {
                    que.push(to);
                    vis[s] = 1;
                }
            }
        }
    }
    return true;
}

int main()
{
    cin >> n >> m;
    for (ll i = 1; i <= m;i++) {
        ll fr, to, w;
        cin >> to >> fr >> w;
        G[fr].push_back({to, w});
    }
    //创建源点
    for (ll i = 1; i <= n;i++) {
        G[0].push_back({i, 0});
    }

   if (spfa(0)) {
       for (ll i = 1; i <= n;i++) {
           cout << dis[i] << " ";
       }
   }else {
    cout << "NO" << endl;
   }

    return 0;
}