#include<stdio.h>
#include<vector>
#include<algorithm>
#include<queue>

using namespace std;

#define NMAX 50005

typedef struct 
{
	int nod,c;
} p;
vector <p> g[NMAX];
bool ut[NMAX];
vector <int> cost(NMAX,(1<<30));
int n,m,steps;

queue <int> Q;

int main()
{
	freopen("bellmanford.in","r",stdin);
	freopen("bellmanford.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		p y;
		int x;
		scanf("%d%d%d",&x,&y.nod,&y.c);
		g[x].push_back(y);
	}
	cost[1]=0;
	Q.push(1);
	ut[1]=1;
	vector <p> ::iterator it;
	while(!Q.empty()&&steps<=1LL*n*m)
	{
		int nod=Q.front();
		Q.pop();
		ut[nod]=0;
		for(it=g[nod].begin();it!=g[nod].end();it++)
		{
			if(cost[it->nod]<=cost[nod]+it->c)
				continue;
			cost[it->nod]=cost[nod]+it->c;
			if(!ut[it->nod])
			{
				ut[it->nod]=1;
				Q.push(it->nod);
			}
			++steps;
		}
	}
	for(int i=1;i<=n;i++)
	{
		for(it=g[i].begin();it!=g[i].end();it++)
			if(cost[i]+it->c<cost[it->nod])
			{
				printf("Ciclu negativ!\n");
				return 0;
			}
	}
	for(int i=2;i<=n;i++)
		printf("%d ",cost[i]);
	return 0;
}