#include<cstdio>
#include<vector>
#include<queue>
using namespace std;
FILE*f=fopen("bellmanford.in","r");
FILE*g=fopen("bellmanford.out","w");
vector < pair<int,int> > v[50001];
queue <int> q;
int n,m,nr[50001],viz[50001],dist[50001],a,b,c;
int main()
{
	fscanf(f,"%d%d",&n,&m);
	for(int i=1;i<=m;++i)
	{
		fscanf(f,"%d%d%d",&a,&b,&c);
		v[a].push_back (make_pair(b,c));
	}
	for(int i=2;i<=n;++i)
		dist[i]=250000000;
		
	q.push (1);	
	int ok=1;
	nr[1]=viz[1]=1;
	
	
	while(ok&&q.size()>0)
	{
		int nod=q.front();
		for(int i=0;i<v[nod].size();++i)
		{
			if(dist[v[nod][i].first]>dist[nod]+v[nod][i].second)
			{
				if(!viz[v[nod][i].first])
				{
					q.push (v[nod][i].first);
					viz[v[nod][i].first]=1;
				}
				
				nr[v[nod][i].first]++;
				dist[v[nod][i].first]=dist[nod]+v[nod][i].second;
				if(nr[v[nod][i].first]>=n)
				{
					ok=0;
					break;
				}
			}
			
		}
		viz[nod]=0;
		q.pop();
	}
	if(!ok)
		fprintf(g,"Ciclu negativ!");
	else
		for(int i=2;i<=n;++i)
			fprintf(g,"%d ",dist[i]);
	
	
	fclose(f);
	fclose(g);
	return 0;
}