#include <stdio.h> //dijkstra
#include <vector>
#define max 500010
#define inf 1<<30
using namespace std;
FILE*f=fopen("dijkstra.in","r");
FILE*g=fopen("dijkstra.out","w");

int i,n,m,j,minim,viz[max],dist[max],k,nod1,nod2,cost,poz;
vector< pair <int,int> > graf[max];

void citire(){
	fscanf(f,"%d %d",&n,&m);
	for(i=0;i<m;i++){
		fscanf(f,"%d %d %d",&nod1,&nod2,&cost);
		graf[nod1].push_back(make_pair(nod2,cost));
	}
}

void dijkstra(int s){
	for(i=1;i<=n;i++){
		dist[i]=inf;
	}
	dist[s]=0;
	for(i=1;i<=n;i++){
		minim = inf;
		for(j=1;j<=n;j++){
			if(!viz[j] && minim>dist[j]){
				minim = dist[j];
				poz = j;
			}
		}
		viz[poz]=1;
		for(j=0;j<graf[poz].size();j++){
			if(!viz[graf[poz][j].first] && dist[graf[poz][j].first] > dist[poz] + graf[poz][j].second){
				dist[graf[poz][j].first]=dist[poz] + graf[poz][j].second;
			}
		}
	}
}

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

int main(){
	
	citire();
	dijkstra(1);
	afis();
	
	fclose(f);
	fclose(g);
	return 0;
}