#include<cstdio>
using namespace std;
#define maxn 50005
#define maxm 250005
#define maxx 50000005
int n,m,ok2;
long long int e[maxm][3],d[maxm],t[maxm];
void bellman(int sursa){
	d[sursa]=0;
	long long int ok=1,i,j,c;
	for(int nr=1;nr<n && ok;++i){
		ok=0;
		for(int k=0;k<m;++k){
			i=e[k][0];
			j=e[k][1];
			c=e[k][2];
			if(d[j]>d[i]+c)
				d[j]=d[i]+c,ok=1,t[j]=i;
		}
	}
		for(int k=0;k<m;++k){
			i=e[k][0];
			j=e[k][1];
			c=e[k][2];
			if(d[j]>d[i]+c){
				printf("Ciclu negativ!");
				k=m;
				ok2=1;
			}
		}
}
int main(){
	freopen("bellmanford.in","r",stdin);
	freopen("bellmanford.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=0;i<m;++i){
		scanf("%lld%lld%lld",&e[i][0],&e[i][1],&e[i][2]);
		if(i<=n)
			d[i]=maxx;
	}
//	for(int i=1;i<=n;++i)
	//	d[i]=maxx;
	bellman(1);
	if(!ok2)
		for(int i=2;i<=n;++i)
			printf("%lld ",d[i]);
	return 0;
}