#include<cstdio>
#include<queue>
#include<vector>
using namespace std;

#define NMAX 50001
#define INF 2000000001
FILE *f=fopen("bellmanford.in","r");
FILE *g=fopen("bellmanford.out","w");

long n,m,d[NMAX],nrq[NMAX],viz[NMAX];
struct muchie{ long nr,cost;};
vector<muchie> L[NMAX];
queue<long> q;


int bford()
{
	for (long i=2;i<=n;i++)
     d[i]=INF;
	
	viz[1]=1;
	q.push(1);
	nrq[1]++;
	
	for (long i=1;i<=n-1;i++)
	{
		long nod=q.front();
		q.pop();
		viz[nod]=0;
		
		for (long j=0;j<L[nod].size();j++)
			{ long vec=L[nod][j].nr,c=L[nod][j].cost;
				 if (d[vec]>d[nod]+c)
					{ d[vec]=d[nod]+c;
				      if (!viz[vec])
						       if (nrq[vec]>n)
							        return 1;
						       else
							      { q.push(vec); viz[vec]=1; nrq[vec]++;}
					}
			}
	}
return 0;}

int main()
{
	fscanf(f,"%ld%ld",&n,&m);
		for (long i=1;i<=m;i++)
		{muchie x;
         long y;		
		fscanf(f,"%ld%ld%ld",&y,&x.nr,&x.cost);
		L[y].push_back(x);
		}
		
	if ( !bford() )
	   for (long i=2;i<=n;i++)
		   fprintf(g,"%ld ",d[i]);
	else
		fprintf(g,"Ciclu negativ!");
	
		   
		
return 0;}