#include <stdio.h>
#include <vector>
#define INF 2000000000
#define MAXX 50001
using namespace std;
FILE*f=fopen("dijkstra.in","r");
FILE*g=fopen("dijkstra.out","w");
struct nodd{
	int nod,cost;
} aux;
vector < nodd > graf[MAXX];

int n,m,i,j,dist[MAXX],viz[MAXX],minn,p;


void citire(){
	int nod1;
	fscanf(f,"%d %d",&n,&m);
	for(i=1;i<=m;i++){
		fscanf(f,"%d %d %d",&nod1,&aux.nod,&aux.cost);
		graf[nod1].push_back(aux);
	}
	/*for(i=1;i<=n;i++){
		for(j=0;j<graf[i].size();j++)
			printf("%d,%d  ",graf[i][j]);
		printf("\n");
	}*/
}

void dijkstra(){
	for(i=1;i<=n;i++){
		dist[i]=INF;
	}
	dist[1]=0;
	for(i=1;i<=n;i++){
		minn=INF;
		for(j=1;j<=n;j++)
			if(dist[j]<minn && !viz[j]){
				minn=dist[j];
				p=j;
			}
		/*if(minn==INF)
			break;*/
		viz[p]=1;
		for(j=0;j<graf[p].size();j++){
			if(/*!viz[graf[p][j].nod] && */dist[graf[p][j].nod]>dist[p]+graf[p][j].cost){
				dist[graf[p][j].nod]=dist[p]+graf[p][j].cost;
			}
		}
	}
}

int main(){
	
	citire();
	dijkstra();
	for(i=2;i<=n;i++){
		if(dist[i]==INF){
			fprintf(g,"0 ");
		}
		else 
			fprintf(g,"%d ",dist[i]);
	}
	fclose(f);
	fclose(g);
	return 0;
}