#include<stdio.h>
using namespace std;
#define dim 5000//0
#define dim2 250000 
#define inf   1005

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()
{
	//int i, vfmin,j;
	//double dmin;
	init();
	/*
	//dijkstra
	for(j=1;j<n;j++)
	{
		dmin=inf;
		for(i=1;i<=n;i++)
			if(!M[i]&&dmin>d[i])
			{
			dmin=d[i];
			vfmin=i;		
			}	
		M[vfmin]=1;
		for(i=1;i<=n;i++)
			if(!M[i]&&d[i]>dmin+C[vfmin][i])
				d[i]=dmin+C[vfmin][i];
			
		
	}
	*/
	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,"costul drumului de cost minim de la %d la %d este %.f \n",x0,i,d[i]);
		
		fprintf(g,"%.f ",d[i]);
		
		//fprintf(g,"drumul de cost minim: \n");
//		dr[0]=i; lg=0;
//		while( pre[ dr[ lg ] ] )
//		{	lg++;
//			dr[ lg ]=pre[ dr[ lg-1 ] ];		}
		
	//	for(j=lg;j>=0;j--)
	//		fprintf(g," %d\n",dr[j]);
		
	}
	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;
}