#include<stdio.h>
using namespace std;
#define dim 5000
#define inf 5000000

int n,pre[dim],ok,C[dim][dim],d[dim];

void init();
void afisare();
int bellmanford();

FILE *f=fopen("bellmanford.in","r"),*g=fopen("bellmanford.out","w");

int main()
{
	
	init();
	
	if(!bellmanford())
	{
	afisare();
	}
	else fprintf(g,"Ciclu negativ!\n");
	
return 0;
}


void init()
{
	int i,j,m,x,y,c;
	
	fscanf(f,"%d %d",&n,&m);

	for(i=1;i<=n;i++)
		for(j=i+1;j<=n;j++)
			C[j][i]=C[i][j]=inf;
		
	for(i=1;i<=m;i++)
	{
	fscanf(f,"%d %d %d",&x,&y,&c);
	C[x][y]=c;
	}
	
	for(i=1;i<=n;i++)
	{
	d[i]=C[1][i]; pre[i]=1;
	}
	pre[1]=0;
	
	
fclose(f);
}

void afisare()
{
int i;
for(i=2;i<=n;i++)
	if(d[i]!=inf)
		fprintf(g,"%d ",d[i]);
	else fprintf(g,"0 ");
	fprintf(g,"\n");
fclose(g);

}

int bellmanford()
{
	int i,j,k;
	for(i=1;i<=n;i++)
		{ok=0;  
	for(j=1;j<=n;j++)
	for(k=1;k<=n;k++)
		if(C[j][k]!=inf&&d[k]>d[j]+C[j][k])	
		{
		d[k]=d[j]+C[j][k];
		pre[k]=j;
		ok=1;
		}
		}
if(ok) return 1;
return 0;
}