#include<fstream>
using namespace std;
fstream f1,f2;
int n,m,viz[50001],list[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,p,u;
	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);
	}
	list[1]=1;
	p=1;
	u=1;
	dist[1]=0;
	while(p<=u)
	{
		viz[list[p]]=1;
		for(q=a[list[p]];q!=0;q=q->adresa)
		{
			y=q->z;
			d=q->d;
			if(viz[y]==0 && d+dist[list[p]]<dist[y])
			{
				u++;
				list[u]=y;
				dist[y]=d+dist[list[p]];
			}
		}
		p++;
	}
	for(i=2;i<=n;i++)
		f2<<dist[i]<<" ";
	f1.close();
	f2.close();
	return 0;
}