#include<iostream>
#include<fstream>
using namespace std;
struct nod
{
	int vf,val;
	nod *next;
};
#define nn 50005
#define inn 1<<10
nod *g[nn];
int d[nn],h[nn],poz[nn],n,m;
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 i)
{
	int pp=0;
	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 i)
{
	int pp=0;
	for(;!pp&&i*2<=m;)
	{
		int k=i*2;
		if(d[h[i]]<d[h[k]])
			pp=1;
		else
		{
			if(k+1<=m&&d[h[k+1]]<d[h[k]])
				++k;
			int aux=h[i];
			h[i]=h[k];
			h[k]=aux;
			poz[h[i]]=i;
			poz[h[k]]=k;
			i=k;
		}
	}
}
void start()
{
	for(int i=1;i<=n;++i)
		d[i]=inn,h[i]=i,poz[i]=i;
	m=n;
	d[1]=0;
	h[1]=h[m--];
	poz[h[1]]=1;
	cerne(1);
	for(nod*p=g[1];p;p=p->next)
	{
		d[p->vf]=p->val;
		promoveaza(poz[p->vf]);
	}
}
void dijkstra()
{
	start();
	int pmin;
	for(int i=1;i<=n;++i)
	{
		pmin=h[1];
		if(d[pmin]==inn)
			break;
		poz[h[1]]=1;
		cerne(1);
		for(nod*p=g[i];p;p=p->next)
			if(d[pmin]+p->val<d[p->vf])
			{
				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);
	}
	dijkstra();
	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;
}