#include<cstdio>
#include<vector>
#include<queue>
#include<bitset>
using namespace std;
#define INF 999999
#define maxn 50005
#define maxm 250005
FILE *f=fopen("bellmanford.in","r");
FILE *g=fopen("bellmanford.out","w");
vector <int> G[maxm],C[maxm],d(maxn,INF),nrap(maxn,0);
queue <int> Q;
bitset <maxn> incoada(false);
//<bitset>
int n,m,x,y,c;
bool negative=false;
void bell(){
	d[1]=0;
	Q.push(1);
	incoada[1].flip();
	while(Q.empty()==0 && negative==false){
		int x=Q.front();
		Q.pop();
		incoada[x]=false;
		for(int i=0;i<G[x].size();i++)
			if(d[x]!=INF)
			if(d[G[x][i]]>C[x][i]+d[x]){
				d[G[x][i]]=C[x][i]+d[x];
				if(!incoada[G[x][i]])
					if(nrap[G[x][i]]==n)
						negative=true;
					else
					{
						Q.push(G[x][i]);
						nrap[G[x][i]]++;
						incoada[G[x][i]]=true;
					}
				}
	}
}
int main (){
	fscanf(f,"%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		fscanf(f,"%d%d%d",&x,&y,&c);
		G[x].push_back(y);
		C[x].push_back(c);
	}
	bell();
	if(negative==true)
		fprintf(g,"Ciclu negativ!\n");
	else
		
	for(int i=2;i<=n;i++)
		fprintf(g,"%d ",d[i]);
	return 0;
}