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

struct{
	int x;
	int y;
	int c;
} arc[250001];

int i,ok,m,n,dist[50001];

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

void bellmanford(int s){
	for(i=1;i<=n;i++){
		dist[i] = inf;
	}
	dist[s]=0;
	while(!ok){
		ok=1;
		for(i=1;i<=m;i++){
			if(dist[arc[i].y]>dist[arc[i].x]+arc[i].c){
				dist[arc[i].y]=dist[arc[i].x]+arc[i].c;
				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;
}