#include<bits/stdc++.h>
using namespace std;
const int maxn=6*1e3,mod=1*1e4;
int n,h,b[maxn],e[maxn],t[maxn],sum,di[maxn];
int cnt[maxn],cntt[maxn],first[maxn],next[maxn];
queue<int>q;
void add(int x,int y,int z)
{
	b[sum]=x;
	e[sum]=y;
	t[sum]=z;
	next[sum]=first[x];
	first[x]=sum;
	sum++;
}
int main()
{
	cin>>n>>h;
	for(int i=0;i<=n;i++)
	first[i]=-1;
	for(int i=0;i<h;i++)
	{
		int x,y,z;
		cin>>x>>y>>z;
		add(y,x,z);
	//	add(x,y,-z);
	}
	for(int i=1;i<=n;i++)
	add(0,i,0);
	memset(di,mod,sizeof(di));
	di[0]=0;
	cnt[0]=1;
	cntt[0]=1;
	q.push(0);
	while(!q.empty())
	{
		int x=q.front();
		//cout<<x<<endl;
		cnt[x]=0;
		q.pop();
		int k=first[x];
		while(k!=-1)
		{
			//cout<<b[k]<< " "<<e[k]<<endl;
			if(di[e[k]]>di[b[k]]+t[k])
			{
				di[e[k]]=t[k]+di[b[k]];
				if(cnt[e[k]]==0)
				{
					q.push(e[k]);
					cnt[e[k]]=1;
					cntt[e[k]]++;
					if(cntt[e[k]]>=n)
					{
					cout<<"NO"<<endl;
					return 0;	
					}
				}
			}
			k=next[k];
		}
	}
	for(int i=1;i<=n;i++)
	cout<<di[i]<<" ";
	return 0;
}