#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define SIZE 1000001
     
struct road{
    ll ver,cost;
};

ll n,m;
ll dis[SIZE];
ll times[SIZE];
bool vis[SIZE];
vector<road> r[SIZE];

bool spfa(ll root){
    queue<ll> q;
    q.push(root);
    dis[root]=0;
    vis[root]=1;
    while(!q.empty()){
        ll x=q.front();q.pop();
        vis[x]=0;

        for(ll i=0;i<r[x].size();i++){
            ll y=r[x][i].ver;
            ll z=r[x][i].cost;
            
            if(dis[y]>dis[x]+z){
                dis[y]=dis[x]+z;

                if(!vis[y]){
                    times[y]=times[x]+1;
                    q.push(y);
                    vis[y]=1;

                    if(times[y]>n)
                    return true;
                }
            }
        }
    }
    return false;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);

    memset(dis,0x7f,sizeof(dis));
    cin>>n>>m;
    for(ll i=1;i<=m;i++){
        ll x;road y;
        cin>>x>>y.ver>>y.cost;
        r[x].push_back(y);
    }

    for(ll i=1;i<=n;i++){
        road y;
        y.ver=i;
        y.cost=0;
        r[0].push_back(y);
    }

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