#include<fstream>
#include<iostream>
using namespace std;
struct nod
{
	int vf;
	int val;
	nod *next;
};
#define nn 50005
#define inn 1<<10
nod *g[nn];
int n,m,d[nn],h[nn],poz[nn];//,v[nn];//,t[nn];
void adauga(int a,int b,int c)
{
	nod*p=new nod;
	p->vf=b;
	p->val=c;
	p->next=g[a];
	g[a]=p;
}
void promoveaza(int x)
{
	int pp=0,i=m;
	for(;!pp&&i>1;)
		if(d[h[i]]>d[h[i/2]])
			pp=1;
		else
		{
			int aux=h[i];
			h[i]=h[i/2];
			h[i/2]=aux;
			poz[h[i]]=i;
			poz[h[i/2]]=i/2;
			i/=2;
		}
}
void cerne(int x)
{
	int pp=0,i=x;
	for(;!pp&&i*2<=m;)
	{
		int k=i*2;
		if(k+1<=m&&d[h[k]]>d[h[k+1]])
			++k;
		if(d[h[i]]<d[h[k]])
		pp=1;
		else
		{
			int aux=h[i];
			h[i]=h[k];
			h[k]=aux;
			poz[h[i]]=i;
			poz[h[k]]=k;
			i=k;
		}
	}
}
void init()
{
	for(int i=1;i<=n;++i)
	{
		d[i]=inn;
		h[i]=i;
		poz[i]=i;
		//v[i]=0;
		//t[i]=-1;
	}
	m=n;
	d[1]=0;
	//t[1]=0;
	h[1]=h[--m];
	cerne(1);
	for(nod *p=g[1];p;p=p->next)
	{
		d[p->vf]=p->val;
		//t[p->vf]=1;
		promoveaza(poz[p->vf]);
	}
}
void dijsktra()
{
	init();
	int pmin;
	for(int i=1;i<=n;++i)
	{
		pmin=h[1];
		if(d[pmin]==inn)
			break;
		//v[pmin]=1;
		poz[h[1]]=1;
		cerne(1);
		for(nod *p=g[pmin];p;p=p->next)
		if(d[pmin]+p->val<d[p->vf])
		{
			//t[p->vf]=pmin;
			d[p->vf]=d[pmin]+p->val;
			promoveaza(poz[p->vf]);
		}
		
	}
}
int main()
{
	int a,b,c;
	ifstream fin("dijkstra.in");
	fin>>n>>m;
	for(;m;--m)
	{
		fin>>a>>b>>c;
		adauga(a,b,c);
	}
	dijsktra();
	FILE *f=fopen("dijkstra.out","w");
	for(int i=2;i<=n;++i)
		if(d[i]!=inn)
			fprintf(f,"%d ",d[i]);
		else fprintf(f,"0 ");
	return 0;
}