#include<bits/stdc++.h>
#define N 500005
#define inf 1000000007
using namespace std;
struct node{
	int to,val;
	friend bool operator <(node a,node b){
		return a.val>b.val;
	}
};
int n,m,s,dis[N],cnt[N],vis[N];
vector<node>g[N];
priority_queue<node>q;
void spfa()
{
	for(int i=1;i<=n;i++)
	dis[i]=inf;
	q.push({s,0});
	dis[s]=0;
	while(!q.empty())
	{
		int u=q.top().to;
		vis[u]=1;
		q.pop();
		for(int i=0;i<g[u].size();i++)
		{
			int v=g[u][i].to,w=g[u][i].val;
			if(dis[u]+w<=dis[v])
			{
				dis[v]=dis[u]+w;
				cnt[v]=cnt[u]+1;
				if(cnt[v]>=n){
					cout<<"NO";
					exit(0);
				}
				if(!vis[v]){
					q.push({v,dis[v]});
					vis[v]=1;
				}
			}
		}
	}
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int x,y,z;
		cin>>x>>y>>z;
		g[y].push_back({x,z});
	}
	s=n+1;
	for(int i=1;i<=n;i++)
	g[s].push_back({i,0});
	spfa();
	for(int i=1;i<=n;i++)
	cout<<dis[i]<<' ';
	return 0;
}