#include<fstream.h>
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
#define max 250003
struct muchie{long x,y,cost;}a[max];
long n,m,d[50003],dd[500][500];
int main()
{
	fin>>n>>m;
	long i,g,b,cc;
	for(i=1;i<=m;i++)
	{
		fin>>g>>b>>cc;
		a[i].x=g;
		a[i].y=b;
		a[i].cost=cc;
	    if(g==1)
	//	{
			d[b]=cc; //dd[b][1]=1;dd[b][2]=b;}
    }
	for(i=2;i<=n;i++)
		if(d[i]==0)
			d[i]=max;
//	for(cc=1;cc==1;)
//	{
//		cc=0;
		for(i=1;i<=m;i++)
			if(d[a[i].y]>d[a[i].x]+a[i].cost)
			{
				d[a[i].y]=d[a[i].x]+a[i].cost;

			//	cc=1;
			}
//	}
	for(i=2;i<=n;i++)
		if(d[i]==max)
			fout<<"0 ";
		else 
			fout<<d[i]<<" ";
	fin.close();
	fout.close();
	return 0;
}