#include <stdio.h>
#include <vector>
#include <queue>
#define NMAX 50005
#define INF 2000000000
using namespace std;
typedef struct {int v,c;} MUCHIE;
int n,m;
int COST[NMAX],NR[NMAX],VIZ[NMAX];
bool negative;
vector <MUCHIE> A[NMAX];
queue <int> Q;
FILE *f,*g;
void read()
{
	int i,x;
	MUCHIE a;
	fscanf(f,"%d %d",&n,&m);
	for (i=1;i<=m;++i)
	{
		fscanf(f,"%d %d %d",&x,&a.v,&a.c);
		A[x].push_back(a);
	}
}
void solve()
{
	negative=false;
	vector <MUCHIE> :: iterator it;
	int x;
	Q.push(1);
	NR[1]=1;
	VIZ[1]=1;
	for (int i=1;i<=n;++i)
		COST[i]=INF;
	COST[1]=0;
	while (!Q.empty())
	{
		x=Q.front();
		Q.pop();
		VIZ[x]=0;
		for (it=A[x].begin();it!=A[x].end();++it)
			if (COST[x]+(*it).c<COST[(*it).v])
			{
				COST[(*it).v]=COST[x]+(*it).c;
				NR[(*it).v]++;
				if (!VIZ[(*it).v])
				{
					Q.push((*it).v);
					VIZ[(*it).v]=1;
				}
				if (NR[(*it).v]>=n)
				{
					negative=true;
					return;
				}
			}
	}
}
void print()
{
	int i;
	if (negative)
	{
		fprintf(g,"Ciclu negativ!");
		fprintf(g,"\n");
	}
	else
	{
		for (i=2;i<=n;++i)
			fprintf(g,"%d ",COST[i]);
		fprintf(g,"\n");
	}
}
int main()
{
	f=fopen("bellmanford.in","r");
	g=fopen("bellmanford.out","w");
	read();
	solve();
	print();
	fclose(f);
	fclose(g);
	return 0;
}