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

int n,m,x0,pre[dim];
double C[dim][dim];
int M[dim];
double d[dim];

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

struct C 
{
	double nod[dim];
	int X[dim],Y[dim];
} coada;

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,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;
	coada.nod[i]=c;
	coada.X[i]=x;
	coada.Y[i]=y;
	}
	
	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,sf,in,SF;
	in=1; sf=m;
	
	while(in<=sf)
	{SF=sf;	
	while(in<=SF)
	{ i=in;
		for(j=i;j<=SF;j++)
			for(k=i;k<=SF;k++)
			if(d[coada.Y[k]]>d[coada.X[j]]+C[coada.X[j]][coada.Y[k]]) //imbuntateste costul
			{d[coada.Y[k]]=d[coada.X[j]]+C[coada.X[j]][coada.Y[k]];
			pre[k]=coada.X[j];
			
			coada.nod[++sf]=d[j]+C[j][k];
			coada.X[sf]=coada.X[j];
			coada.Y[sf]=coada.Y[k];
			}
		in++;
	}
	in=SF+1;
	}
			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;
}