#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,j,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;
	for(i=1;i<n;i++){
		for(j=1;j<=m;j++){
			if(dist[arc[j].y]>dist[arc[j].x]+arc[j].c){
				dist[arc[j].y]=dist[arc[j].x]+arc[j].c;
			}
		}
	}
}

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

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