#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e3+5;
int n,m;
struct edge {
	int to,nxt,w;
} a[N];
int head[N],tmp;
bool f=1;
void add(int x,int y,int z) {
	tmp++;
	a[tmp].to=y;
	a[tmp].w=z;
	a[tmp].nxt=head[x];
	head[x]=tmp;
}
bool vis[N];
int cnt[N],dis[N];
void spfa() {
	for(int i=1;i<=n+1;i++) dis[i]=0x7fffffffffffffff,vis[i]=0,cnt[i]=0;
	queue<int>q;
	q.push(n+1);
	vis[n+1]=1,dis[n+1]=0,cnt[n+1]++;
	while(!q.empty()) {
		int now=q.front();
		q.pop();
		vis[now]=0;
		for(int i=head[now]; i; i=a[i].nxt) {
			int u=a[i].to;
			if(dis[u]>dis[now]+a[i].w) {
				dis[u]=dis[now]+a[i].w;
				if(!vis[u]) {
					vis[u]=1;
					q.push(u);
					cnt[u]++;
					if(cnt[u]>=n+1) {
						puts("NO");
						exit(0);
					}
				}
			}
		}
	}
}
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	for(int i=1,x,y,z; i<=m; i++) {
		cin>>x>>y>>z;
		add(y,x,z);
	}
	for(int i=1; i<=n; i++) add(n+1,i,0);
	spfa();
	for(int i=1; i<=n; i++)
		cout<<dis[i]<<' ';
}