#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef long double LD;
const int INF = 2147483647;
const int S = 1e5+5;
int n,m,tot;
int head[S],ver[S],edge[S],Next[S],dis[S],vis[S],v[S];
inline void add(int x,int y,int z)
{ver[++tot] = y,edge[tot] = z,Next[tot] = head[x],head[x] = tot;}
inline bool spfA(int s)
{
    queue <int> q;
    while(!q.empty()) q.pop();
    dis[s] = 0; 
    vis[s] = v[s] = 1;
    q.push(s);
    while(!q.empty())
    {
        int x = q.front();
        q.pop();
        vis[x] = 0;
        for(int i = head[x];i;i = Next[i])
        {
            int y = ver[i],z = edge[i];
            if(dis[y] > (LL)dis[x]+z)
            {
                dis[y] = dis[x]+z;
                if(!vis[y])
                {
                    q.push(y);vis[y] = 1;
                    if(++v[y] > n+1) return true;
                }
            }
        }
    }
    return false;
}
inline LL read()
{
    LL x=0,f=1;
    char ch = getchar();
    while(!isdigit(ch)) {if(ch == '-') f = -1;ch = getchar();}
    while(isdigit(ch)) {x=x*10+ch-48;ch=getchar();}
    return f*x;
}
int main(int argc,char *argv[])
{ 
    //freopen("data.in","r",stdin);
    //freopen("data.out","w",stdout);   
    memset(dis,0x7f,sizeof(dis));memset(vis,0,sizeof(vis));memset(v,0,sizeof(v));
    memset(head,0,sizeof(head));memset(edge,0,sizeof(edge));memset(Next,0,sizeof(Next));
    n = read(),m = read();
    for(int i = 1;i <= m;++i)
    {
        int a = read(),b = read(),c = read();
        add(b,a,c);
    }
    for(int i = 1;i <= n;++i) add(0,i,0);
    if(!spfA(0)) for(int i = 1;i <= n;++i) printf("%d ",dis[i]);
    else puts("NO");
    //printf("Tide used = %.0lf.ds\n",((double)clock()/(double)CLOCKS_PER_SEC) * 1000.0);
    return 0;
}