#include<bits/stdc++.h>
#include<cstdio>
using namespace std;
int c[5001][5001],n,m,f[5001],rd[5001];
bool z[5001];
vector<int> l[5001];
int main()
{
	memset(f,0x7f,sizeof(f));
	memset(rd,0,sizeof(rd));
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		c[0][i]=0,l[0].push_back(i);
	for(int i=1;i<=m;i++)
	{
		int a,a_,y;
		cin>>a>>a_>>y;
		c[a_][a]=y;
		l[a_].push_back(a);
	}
	z[0]=1;f[0]=0;rd[0]=1;
	queue<int> qwe;
	qwe.push(0);
	while(!qwe.empty())
	{
		int u=qwe.front();
		qwe.pop();
		z[u]=0;
		int zxc=l[u].size();
		for(int i=0;i<zxc;i++)
			if(f[u]+c[u][l[u][i]]<f[l[u][i]])
			{
				f[l[u][i]]=f[u]+c[u][l[u][i]];
				if(!z[l[u][i]])
				{
					rd[l[u][i]]++;
					if(rd[l[u][i]]>n)
					{
						cout<<"NO";
						return 0;
					};
					qwe.push(l[u][i]);
					z[l[u][i]]=1;
				}
			}	
	}
	for(int i=1;i<=n;i++)
		cout<<f[i]<<" "; 
}

求大佬康康错哪了