#include<cstdio>
#include<cstdlib>
#include<queue>
using namespace std;
typedef struct {int la,cost;}GRAF;
GRAF* gr[50001];
bool viz[50001];
int nviz[50001];
int d[50001];
queue <int> qn;
bool bellmanford(int n,int s)
{
	int i,y,c;
	d[s]=0;
	qn.push(s);
	viz[s]=1;
	nviz[s]=1;
	while(!qn.empty())
	{
		s=qn.front();
		qn.pop();
		viz[s]=0;
		for(i=1;i<=gr[s][0].la;i++)
		{
			y=gr[s][i].la;
			c=gr[s][i].cost;
			if(d[y]>(d[s]+c))
			{
				nviz[y]++;
				d[y]=d[s]+c;
				if(nviz[y]>=n)
					return 0;
				if(!viz[y])
				{
					qn.push(y);
					viz[y]=1;
				}
			}
		}
	}
	return 1;
}
int main()
{
	int n,m,i,x,y,c;
	int inf=100000000;
	freopen("bellmanford.in","r",stdin);
	scanf("%d %d\n",&n,&m);
	for(i=1;i<=n;i++)
	{
		gr[i]=(GRAF*)realloc(gr[i],8);
		gr[i][0].la=0;
		d[i]=inf;
	}
	for(i=1;i<=m;i++)
	{
		scanf("%d %d %d\n",&x,&y,&c);
		gr[x][0].la++;
		gr[x]=(GRAF*)realloc(gr[x],(gr[x][0].la+1)*8);
		gr[x][gr[x][0].la].la=y;
		gr[x][gr[x][0].la].cost=c;
	}
	fclose(stdin);
	freopen("bellmanford.out","w",stdout);
	if(!bellmanford(n,1))
		printf("Ciclu negativ!");
	else
		for(i=2;i<=n;i++)
			printf("%d ",d[i]);
	printf("\n");
	fclose(stdout);
	return 0;
}