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

int n,x0,pre[dim];
double C[dim][dim];
int M[dim];
double 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;
	double c;
	
	fscanf(f,"%d %d",&n,&m);
	x0=1;
	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 %lf",&x,&y,&c);
	C[x][y]=c;
	}
	
	for(i=1;i<=n;i++)
	{
	d[i]=C[x0][i];
	}
	
	M[x0]=1; 
	
fclose(f);
}

void afisare()
{
int i;
for(i=1;i<=n;i++)
	if(i!=x0)
		fprintf(g,"%.f ",d[i]);
	
	fprintf(g,"\n");
fclose(g);

}

int bellmanford()
{
	int i,j,k;
	for(i=1;i<=n;i++)
		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;
			}
			for(j=1;j<=n;j++)
				for(k=1;k<=n;k++)
					if(C[j][k]!=inf&&d[k]>d[j]+C[j][k])
						return 0;
return 1;
}