#include <cstdio>
using namespace std;
int heap[50001],st[50001],sf[50001],next[250001],dest[250001],cost[250001],d[50001],t[50001],poz[50001];
int x,i,j,n,m;
void change(int p1, int p2)
{
	int aux;
	aux=poz[heap[p1]];
	poz[heap[p1]]=poz[heap[p2]];
	poz[heap[p2]]=aux;
	aux=heap[p1];
	heap[p1]=heap[p2];
	heap[p2]=aux;
}

void upheap(int p)
{
	if((d[heap[p/2]]>d[heap[p]])||(d[heap[p/2]]==0)){
		change(p,p/2);
		upheap(p/2);
												 }
}

void downheap(int p)
{
	if((heap[2*p])||(heap[2*p+1])){
		if((d[heap[2*p]]==0)&&(d[heap[2*p+1]])){change(p,2*p+1);downheap(2*p+1);return;}
		if((d[heap[2*p]])&&(d[heap[2*p+1]]==0)){change(p,2*p);downheap(2*p);return;}
		if(d[heap[2*p]]<d[heap[2*p+1]]){change(p,2*p);downheap(2*p);return;}
		if(d[heap[2*p]]>=d[heap[2*p+1]]){change(p,2*p+1);downheap(2*p+1);return;}
										}
}

int main()
{
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	scanf("%ld%ld",&n,&m);
	for(i=1;i<=m;i++){
		scanf("%ld%ld%ld",&x,&dest[i],&cost[i]);
		if(st[x]==0){st[x]=i;}
		else{next[sf[x]]=i;}
		next[i]=0;sf[x]=i;
					 }
	for(i=1;i<=n;i++){poz[i]=i;heap[i]=i;}
	heap[1]=1;d[1]=1;d[0]=-1;
	while(d[heap[1]]){
		x=heap[1];
		for(i=st[x];i;i=next[i]){
			if((d[dest[i]]==0)&&(t[dest[i]]==0)){
				d[dest[i]]=d[x]+cost[i];
				upheap(poz[dest[i]]);
							 }
			if(d[x]+cost[i]<d[dest[i]]){
				d[dest[i]]=d[x]+cost[i];
				upheap(poz[dest[i]]);
									   }
								}
		t[x]=d[x];d[x]=0;downheap(1);
				  }
	for(i=2;i<=n;i++){
		if(t[i]==0){t[i]++;}
		printf("%ld ",t[i]-1);
					 }
return 0;
}