#include <bits/stdc++.h>
using namespace std;
int n,m,tot,vis[99999],dis[99999],cnt[99999],head[99999];
struct node{
	int v,w,nxt;
}a[99999];
inline void add(int u,int v,int w){
	a[++tot].v=v;
	a[tot].w=w;
	a[tot].nxt=head[u];
	head[u]=tot;
}
signed main(){
	cin>>n>>m;
	for (int i=1,u,v,w;i<=m;i++){
		cin>>v>>u>>w;
		add(u,v,w);
	}
	for (int i=1;i<=n;i++)add(0,i,0);
	queue<int>q;
	q.push(0);dis[0]=0;cnt[0]=1;vis[0]=1;
	while(!q.empty()){
		int x=q.front();q.pop();
		vis[x]=0;
		for (int i=head[x];i;i=a[i].nxt){
			int w=a[i].w,y=a[i].v;
			if (dis[y]>w+dis[x]){
				dis[y]=w+dis[x];
				if (!vis[y]){
					vis[y]=1;
					q.push(y);
					cnt[y]++;
					if (cnt[y]>n){
						cout<<"NO";
						return 0;
					}
				}
			}
		}
	}
	for (int i=1;i<=n;i++)cout<<dis[i]<<" ";
	return 0;
}