#include<fstream>
#define INF 32000
using namespace std;
int a[250001][3],d[50001],n,k,x=1,i,j,c,m,nr=1;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int main()
{
    f>>n>>m;
	for(i=2;i<=n;i++)
		d[i]=INF;
	d[1]=0;
	for(i=1;i<=m;i++)
	{
		f>>a[i][0]>>a[i][1]>>a[i][2];
		if(a[i][0]==1) d[a[i][1]]=a[i][2];
	}
	while(x && nr<n)
	{
		x=0;
			for(k=1;k<=m;k++)
				if(d[a[k][1]]>d[a[k][0]]+a[k][2])
					{d[a[k][1]]=d[a[k][0]]+a[k][2];x=1;}
			nr++;
	}

for(i=2;i<=n;i++) { if(d[i]<INF) g<<d[i]<<" "; else g<<0<<" ";}
f.close();
g.close();
return 0;
}