#include <stdio.h> // BELLMANFORD algoritm
#define inf 1<<30
FILE*f=fopen("dijkstra.in","r");
FILE*g=fopen("dijkstra.out","w");

int i,ok,m,n,dist[50001],x[250001],y[250001],c[250001];

void citire(){
	fscanf(f,"%d %d",&n,&m);
	for(i=1;i<=n;i++){
		dist[i] = inf;
	}
	for(i=1;i<=m;i++){
		fscanf(f,"%d %d %d",&x[i],&y[i],&c[i]);
		if(x[i]==1){
			dist[y[i]]=c[i];
		}
	}
}

void bellmanford(int s){
	dist[s]=0;
	while(!ok){
		ok=1;
		for(i=1;i<=m;i++){
			if(dist[y[i]]>dist[x[i]]+c[i]){
				dist[y[i]]=dist[x[i]]+c[i];
				ok=0;
			}
		}
	}
}

void afisare(){
	for(i=2;i<=n;i++){
		if(dist[i]!=inf)
			fprintf(g,"%d ",dist[i]);
		else
			fprintf(g,"0 ");
	}
}

int main(){
	
	citire();
	bellmanford(1);
	afisare();
	
	fclose(f);
	fclose(g);
	return 0;
}