#include<stdio.h>
#include<vector>
#define nmax 50005
#define inf 2000000000
#define x first
#define c second
#define pb push_back
#define mp make_pair
using namespace std;
int n,m,d[nmax],sw;
vector < pair <int,int> > l[nmax];
void cit(){
	FILE *f;
	int i,a,b,c;
	f=fopen("bellmanford.in","r");
	fscanf(f,"%d%d",&n,&m);
	for(i=1;i<=m;i++){
		fscanf(f,"%d%d%d",&a,&b,&c);
		l[a].pb(mp(b,c));
	}
	fclose(f);
}
int bellman_ford(){
	int i,j,sw;
	for(i=1;i<=n;i++)
		d[i]=inf;
	d[1]=0;
	sw=0;
	for(i=1;i<=n&&!sw;i++){
		sw=1;
		for(j=1;j<=n;j++)
			for(unsigned int k=0;k<l[j].size();k++)
				if(d[l[j][k].x]>d[j]+l[j][k].c){
					sw=0;
					d[l[j][k].x]=d[j]+l[j][k].c;
				}
	}
	return sw;
}
void afis(){
	FILE *f;
	f=fopen("bellmanford.out","w");
	if(sw==0)
		fprintf(f,"Ciclu negativ!\n");
	else
		for(int i=2;i<=n;i++)
			fprintf(f,"%d ",d[i]);
	fclose(f);
}
int main(){
	cit();
	sw=bellman_ford();
	afis();
	return 0;
}