#include <cstdio>
using namespace std;
int st[50001],sf[50001],dest[250001],next[250001],heap[50001][2],dmin[50001],val[250001],p[50001];
int i,v,x,y,poz,n,m,aux;
int min(int x, int y){if(x>y){return y;}return x;}
void addheap(int x)
{
	if((heap[x/2][0]>heap[x][0])||(heap[x/2][0]==0)){
		aux=heap[x][0];
		heap[x][0]=heap[x/2][0];
		heap[x/2][0]=aux;
		
		aux=heap[x][1];
		heap[x][1]=heap[x/2][1];
		heap[x/2][1]=aux;
		
		aux=p[heap[x][1]];
		p[heap[x][1]]=p[heap[x/2][1]];
		p[heap[x/2][1]]=aux;
		
		addheap(x/2);
							   }
}
void remheap(int x)
{
	if((heap[2*x][0]==0)&&(heap[2*x+1][0]==0)){
		heap[x][0]=0;
		heap[x][1]=0;
		return;
											  }
	if((heap[2*x][0]==0)&&(heap[2*x+1][0])){
		heap[x][0]=heap[2*x+1][0];
		heap[x][1]=heap[2*x+1][1];													   
		p[heap[x][1]]=p[heap[2*x+1][1]];
		remheap(2*x+1);
		return;
										   }
	if((heap[2*x][0])&&(heap[2*x+1][0]==0)){
		heap[x][0]=heap[2*x][0];
		heap[x][1]=heap[2*x][1];													   
		p[heap[x][1]]=x;
		remheap(2*x);
		return;
										   }
	if(heap[2*x][0]>heap[2*x+1][0]){
		heap[x][0]=heap[2*x+1][0];
		heap[x][1]=heap[2*x+1][1];													   
		p[heap[x][1]]=p[heap[2*x+1][1]];
		remheap(2*x+1);
		return;
										   }
	if(heap[2*x][0]<heap[2*x+1][0]){
		heap[x][0]=heap[2*x][0];
		heap[x][1]=heap[2*x][1];													   
		p[heap[x][1]]=p[heap[2*x][1]];
		remheap(2*x);
		return;
										   }
}
void add(int x, int y, int v)
{
	if(st[x]){next[sf[x]]=poz;}
	else{st[x]=poz;}
	sf[x]=poz;dest[poz]=y;next[poz]=0;val[poz]=v;
}
int main()
{
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	scanf("%ld%ld",&n,&m);
	for(poz=1;poz<=m;poz++){
		scanf("%ld%ld%ld",&x,&y,&v);
		add(x,y,v);
						   }
	for(i=1;i<=n;i++){
		heap[i][1]=i;p[i]=i;
					 }
	heap[1][0]=1;heap[1][1]=1;
	while(heap[1][0]){
		x=heap[1][1];dmin[x]=heap[1][0];
		for(i=st[x];i;i=next[i]){
			y=dest[i];
			if(dmin[y]==0){
				if(heap[p[y]][0]==0){
					heap[p[y]][0]=dmin[x]+val[i];
					addheap(p[y]);
									  }
				else{
					heap[p[y]][0]=min(dmin[x]+val[i],heap[p[y]][0]);
					addheap(p[y]);
					}
						 }
								}
		remheap(1);
					 }
	for(i=2;i<=n;i++){
		if(dmin[i]){printf("%ld ",dmin[i]-1);}
		else{printf("0 ");}
					 }
return 0;
}