#include<stdio.h>
FILE *in,*out;
const int inf = 1 << 30;
struct graf
{
	int nod, cost;
	graf *next;
};
graf *a[50001];


void add(int where, int what, int cost)
{
	graf *q=new graf;
	q->nod=what;
	q->cost=cost;
	q->next=a[where];
	a[where]=q;	
}


int n,m,x,y,z,d[50001], h[50001], poz[50001], k;

void swap(int x,int y)
{
	int t=h[x];
	h[x]=h[y];
	h[y]=t;
}

void downheap(int what)
{
	int f;
	while( what<=k)
	{
		f=what;
		if((what<<1)<=k)
		{
			f=what<<1;
			if(f+1<=k)
				if(d[h[f+1]]<d[h[f]])
					f++;
		}
		else
			return;
		if(d[h[what]]>d[h[f]])
		{
			poz[h[what]]=f;
			poz[h[f]]=what;
			swap(what,f);
			what=f;
		}
		else
			return;
	}
};

void upheap(int what)
{
	int tata;
	while(what>1)
	{
		tata=what>>1;
		if( d[ h[tata]]>d[what])
		{
			poz[h[what]]=tata;
			poz[ h[tata] ] = what;
			swap(tata, what);
			what = tata;
		}
		else
			what = 1;
	}
};

void dijsktra_heap()
{
	for(int i=2;i<=n;i++)
	{
		d[i]=inf;
		poz[i]=-1;
	}
	h[++k]=1;
	
	while(k)
	{
		int min=h[1];
		swap(1,k);
		poz[ h[1] ]=1;
		--k;
		downheap(1);
		
		graf *q=a[min];
		while(q)
		{
			if( d[q->nod] > d[min] +q->cost)
			{
				d[q->nod]=d[min] +q->cost;
				if(poz[q->nod] !=-1)
					upheap( poz[q->nod]);
				else
				{
					h[++k] = q->nod;
					poz[ h[k] ] = k;
					upheap( k );
				}
			}
			q=q->next;
		}
	}
};
	


int main()
{
	in=fopen("Dijsktra.in","rt");
	out=fopen("Dijsktra.out","wt");
	fscanf(in,"%d %d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		fscanf(in,"%d %d %d",&x,&y,&z);
		add(x,y,z);
	}
	dijsktra_heap();
	for(int i=2;i<=n;i++)
		fprintf(out,"%d ",d[i]==inf?0:d[i]);
	fprintf(out,"\n");
	
	return 0;
}