#include<fstream>
using namespace std;
struct nod{int info,dist; nod*adr;} *v[50001],*p;
int n,m,i,j,x,y,c,d[50001],viz[50001],drum[50001],inf=32767,minn,poz;
void dijkstra(int nod)
{
	p=v[nod];viz[nod]=1;
	for(i=1;i<=n;i++) d[i]=inf;
	while(p)
	{
		d[p->info]=p->dist;
		p=p->adr;
	}
	for(i=1;i<=n-1;i++)
	{
		minn=inf;
		for(j=1;j<=n;j++)
			if(j!=nod && !viz[j] && d[j]<minn)
			{
				minn=d[j];
				poz=j;
			}
		viz[poz]=1;
		p=v[poz];
		while(p)
		{
			if(!viz[p->info] && d[p->info] > p->dist + minn )
			                  {
				                d[p->info] = p->dist + minn;
								d[p->info] = poz;
							  }
			p=p->adr;
		}
	}
}
int main()
{
	ifstream f("dijkstra.in");ofstream g("dijkstra.out");
	f>>n>>m;
	for(i=1;i<=m;i++)
	{
		f>>x>>y>>c;
		p=new nod; p->info=y; p->dist=c; p->adr=v[x]; v[x]=p;
	}
	dijkstra(1);
	for(i=2;i<=n;i++) d[i]==inf?g<<"0 ":g<<d[i]<<" ";
	f.close();g.close();
return 0;}