#include<stdio.h>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;
#define NMAX 50005
#define DIM 4096
typedef struct 
{
	int nod,c;
} p;
vector <p> g[NMAX];
vector <bool> ut(NMAX);
vector <int> cost(NMAX,(1<<30));
int n,m,steps;
struct cmp
{
	bool operator () (const int i,const int j) const
	{
		return cost[i]>cost[j];
	}
};
priority_queue <int,vector <int>,cmp> Q;
char PARSE[DIM];
int poz=DIM-1;
void read(int &x)
{
	x=0;
	int t=0;
	while((PARSE[poz]<'0'||'9'<PARSE[poz])&&PARSE[poz]!='-')
		if(++poz==DIM)
			fread(PARSE,1,DIM,stdin),poz=0;
	if(PARSE[poz]=='-')
	{
		if(++poz==DIM)
			fread(PARSE,1,DIM,stdin),poz=0;
		t=1;
	}
	while('0'<=PARSE[poz]&&PARSE[poz]<='9')
	{
		x=x*10+PARSE[poz]-'0';
		if(++poz==DIM)
			fread(PARSE,1,DIM,stdin),poz=0;
	}
	if(t)
		x=-x;
}
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;
		read(x);read(y.nod);read(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.top();
		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;
}