#include<stdio.h>
#include<vector>
using namespace std;
#define Max 50001
#define Inf 2e8

struct dj
{
	int j,c;
	dj *next;
};

dj *a[Max];
int dis[Max],poz[Max],h[Max];
int n,m,t,x,y,z,k=0;
void add(int i,int j,int c)
{
	dj *d;
	d=new dj;	
	d->j=j;
	d->c=c;
	d->next=a[i];
	a[i]=d;
}
void swap(int x,int y)
{
	int t=h[x];
	h[x]=h[y];
	h[y]=t;
}

void upheap(int ln)
{
	int f;
	while( ln>1 )
	{
		f = ln >> 1;
		if(dis[ h [ f] ] > dis[ h [ ln ] ])
		{
			poz[h[ln]]=f;
			poz[h[f]]=ln;
			swap( f , ln );
			ln=f;
		}
		else ln=1;
	}


}
void downheap(int w)
{
	
	int f;
	
	while(w <= k)
	{
		f = w;
		if( ( w << 1 ) <= k )
		{
			f=w<<1;
			if(f+1 <= k)
				if( dis[ h[f+1] ]<dis[h[f]]) ++f; 
		}
		else
			return;
		if(dis[h[w]]>dis[h[f]])		
		{
			poz[h[w]]=f;

			poz[h[f]]=w;

			swap(w,f);

			w=f;
		}
		else return;
	
	}
}


void djheap()
{
	for(int i=2;i<=n;++i)
	{
		dis[i]=Inf;
		poz[i]=-1;
	}
	dis[1]=0;
	poz[1]=1;
	h[++k]=1;
	int min;
	while(k)
	{
		

		min=h[1]; 
		
		swap(1,k);
		poz[h[1]]=1;
		--k;

		downheap( 1 );
		dj *q=a[min];
		
		while(q)
		{
			
		
		
			if(dis[q->j]>dis[min]+(q->c)) 
			{
				
				dis[q->j]=dis[min]+(q->c);
				if(poz[q->j]!=-1)			upheap(poz[q->j]);
				else
				{
					h[++k]=q->j;
					
					poz[h[k]]=k;
					upheap(k);
				}
			}
			q=q->next;
		}

	}
			
}



int main()
{
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	
	
	scanf("%d",&n);
	scanf("%d",&m);
	
	for(int i=1;i<=m;++i)
	{
		
		scanf("%d %d %d",&x,&y,&z);
		add(x,y,z);
	}

	djheap();
	

	
			
	for(int i=2;i<=n;++i) 
		if(dis[i] == Inf) printf("0 ");
			else printf("%d ",dis[i]);
	return 0;
}