#include<iostream>
#include<fstream>
#define MARE 100000000
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
unsigned short int n,x,y,a[3000][3000],i,j,v[3000],s[3000];
unsigned short int c;
int m;
void dijkstra(int linie)
	{unsigned short int k,minim=1001,d,col,q;
	for(k=1;k<=n;k++)
		v[k]=a[linie][k];
	s[linie]=1;
	v[linie]=0;
	for(k=2;k<=n;k++)
		{minim=MARE;
		for(q=1;q<=n;q++)
			if(s[q]==0)
				if(v[q]<minim)
					{minim=v[q];
					col=q;}
		s[col]=1;
		for(q=1;q<=n;q++)
			if(s[q]==0)
				{d=v[col]+a[col][q];
				if(d<v[q])
					v[q]=d;
				
				}
		}
	}
int main()
{f>>n>>m;
for(i=1;i<=n;i++)
	for(j=1;j<=n;j++)
		if(i!=j)
			a[i][j]=MARE;
for(i=1;i<=m;i++)
	{f>>x>>y>>c;
	a[x][y]=c;
	}
dijkstra(1);
for(i=2;i<=n;i++)
	{if(v[i]==MARE)
		g<<"0 ";
	else g<<v[i]<<" ";}
}