#include<bits/stdc++.h>
#define int long long
#define kong <<' '
using namespace std;
const int N=1e4+5;
int tot,n,m,head[N],dis[N],cnt[N],vis[N],f=1;
struct node{
	int to,ver,nxt;
}tu[N];
void add(int x,int y,int z){
	tu[++tot].to=y;
	tu[tot].ver=z;
	tu[tot].nxt=head[x];
	head[x]=tot; 
}
void spfa(){
	memset(dis,0x3f,sizeof dis);
	dis[0]=0;
	priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > q;
	q.push(make_pair(0,0));
	vis[0]=1;
	while(!q.empty()){
		int x=q.top().second;
		//cout<<x<<endl;
		q.pop();
		vis[x]=0;
		for(int i=head[x];i;i=tu[i].nxt){
			int v=tu[i].to,w=tu[i].ver;
			if(vis[v]) continue;
				//cout<<v<<" "<<x<<" "<<w<<endl;
			if(dis[v]>dis[x]+w){
				dis[v]=dis[x]+w;
				vis[v]=1;
				q.push(make_pair(dis[v],v));
				cnt[i]++;
				if(cnt[i]>n){
					f=0;
					cout<<"NO";
					return ;
				}
			}
		}
	}
}
signed main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int x,y,z;
		cin>>x>>y>>z;
		add(y,x,z);
	}
	for(int i=1;i<=n;i++){
		add(0,i,0);
	}
	spfa();
	if(f) for(int i=1;i<=n;i++) cout<<dis[i]<<' ';
	return 0;
}