#include<stdio.h>
#include<string.h>
#define oo 0x3f3f3f3f
#define DIM 8192
#define mod (1<<16)-1

char ax[DIM];
int pz;

inline void cit(int &x)
{
	x=0;
	while(ax[pz]<'0' || ax[pz]>'9')
		if(++pz==DIM)fread(ax,1,DIM,stdin),pz=0;
	
	while(ax[pz]>='0' && ax[pz]<='9')
	{
		x=x*10+ax[pz]-'0';
		if(++pz==DIM)fread(ax, 1, DIM,stdin),pz=0;
	}
}

struct nod {int b,c; 
			nod *n;};

nod *a[50001];
int n,m,d[50001],i;

void citire()
{
	cit(n);cit(m);
	int p, q, cost;
	
	while(m--)
	{
		cit(p);cit(q);cit(cost);
		nod *t=new nod;
		t->b=q;
		t->c=cost;
		t->n=a[p];
		a[p]=t;
	}
}

void bellman()
{
	memset(d,oo,sizeof(d));
	d[1]=0;
	
	int Q[(1<<16)+13];
	int p=0, q=0;
	bool viz[50001];
	memset(viz,0,sizeof(viz));
	
	Q[0]=1;
	viz[1]=1;
	int x,nr=1;
	nod *it;
	
	while(nr)
	{
		x=Q[p];
		p++;
		p&=mod;
		nr--;
		viz[x]=0;
		for(it=a[x];it;it=it->n)
		{
			if(d[x]+it->c < d[it->b]) 
			{
				d[it->b]=d[x]+it->c;
				if(!viz[it->b])
				{
					viz[it->b]=1;
					q++;
					q&=mod;
					Q[q]=it->b;
					nr++;
				}
			}
		}
	}
	for(i=1;i<=n;i++) if(d[i]==oo) d[i]=0;
	for(i=2;i<=n;i++) printf("%d ",d[i]);
	
	printf("\n");
}

int main()
{
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	
	citire();
	bellman();
	
	return 0;
}