#include <fstream.h>
#define inf 1001
unsigned long n,m,a[20000][20000],x0,d[20000],M[20000],vf=1;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
void citire()
{
	long x,b,c;
	f>>n>>m;
	for(unsigned long i=1;i<=m;i++)
	{
		f>>x>>b>>c;
		a[x][b]=c;
	}
	f.close();
}
void init()
{
	x0=1;
	M[vf]=x0;
	for(unsigned long x=1;x<=n;x++)
		if(a[x0][x]!=0)
			d[x]=a[x0][x];
		else 
			d[x]=inf;
	d[x0]=0;
}
int nu_apartine(unsigned long x)
{
	for(unsigned long i=1;i<=vf;i++)
		if(x==M[i])
			return 0;
	return 1;
}
unsigned long min()
{
	unsigned long minim=inf,imin;
	for(unsigned long i=1;i<=n;i++)
		if(nu_apartine(i) && d[i]<minim)
		{
			minim=d[i];
			imin=i;
		}
	return imin;
}
void prelucrare()
{
	unsigned long x=min();
	M[++vf]=x;
	for(unsigned long y=2;y<=n;y++)
		if(nu_apartine(y) && a[x][y]!=0 && d[y]>d[x]+a[x][y])
			d[y]=d[x]+a[x][y];
}
int main()
{
	citire();
	init();
	for(unsigned long i=1;i<=n;i++)
		prelucrare();
	for(unsigned long i=2;i<=n;i++)
		if(d[i]==inf)
			g<<0<<' ';
		else
			g<<d[i]<<' ';
	g.close();
	return 0;
}