#include<fstream>
using namespace std;
fstream f1,f2;
int n,m,viz[50001],dist[50001];

struct nod
{
	int z,d;
	nod *adresa;
};
nod *a[50001];

void adaug(int x,int y,int d)
{
	nod *p;
	p=new nod;
	p->z=y;
	p->d=d;
	p->adresa=a[x];
	a[x]=p;
}

int main()
{
	nod *q;
	int x,y,d,i,k,min,j;
	f1.open("dijkstra.in",ios::in);
	f2.open("dijkstra.out",ios::out);
	f1>>n>>m;
	for(i=1;i<=n;i++)
	{
		a[i]=0;
		viz[i]=0;
		dist[i]=100000;
	}
	for(i=1;i<=m;i++)
	{
		f1>>x>>y>>d;
		adaug(x,y,d);
	}
	dist[1]=0;
	viz[1]=1;
	for(q=a[1];q!=0;q=q->adresa)
		dist[q->z]=q->d;
	for(k=1;k<=n-1;k++)
	{
		min=1000000;
		for(i=1;i<=n;i++)
			if(viz[i]==0 && dist[i]<min)
			{
				min=dist[i];
				j=i;
			}
		viz[j]=1;
		for(q=a[j];q!=0;q=q->adresa)
		{
			if(viz[q->z]==0 && dist[j]+q->d < dist[q->z])
				dist[q->z]=dist[j]+q->d;
		}
	}
	for(i=2;i<=n;i++)
		if(dist[i]==100000)
			f2<<"0 ";
		else
			f2<<dist[i]<<" ";
	f1.close();
	f2.close();
	return 0;
}