#include<cstdio>
#include<climits>
#include<vector>
#include<algorithm>

#define MAXN 50005
#define inf INT_MAX/2

std :: vector <int> A[MAXN], C[MAXN];
std :: vector <int> :: iterator it,it2;

int N,M;
int D[MAXN],S[MAXN];
int H[MAXN],P[MAXN],Q,X[MAXN];

void read(){
	
	scanf("%d%d",&N,&M);
	
	int x,y,c;
	for(int i=1;i<=M;i++){
		scanf("%d%d%d",&x,&y,&c);
		A[x].push_back(y);
		C[x].push_back(c);
	}
	
}

void Avansare(int n){
	
	while(H[n] < H[n/2] && n/2){
		
		X[P[n]] = n/2;
		X[P[n/2]] = n;
		std :: swap(H[n],H[n/2]);
		std :: swap(P[n],P[n/2]);
		n/=2;
		
	}
	
}

void Retrogradare(int n){
	
	while((H[n] > H[n*2] && Q>n*2) || (H[n] > H[n*2+1] && Q>n*2+1)){
		if(H[n*2] < H[n*2+1]){
			
			X[P[n]] = n*2;
			X[P[n*2]] = n;
			std :: swap(H[n],H[n*2]);
			std :: swap(P[n],P[n*2]);
			n*=2;
			
		}
		else{
			
			X[P[n]] = n*2+1;
			X[P[n*2+1]] = n;
			std :: swap(H[n],H[n*2+1]);
			std :: swap(P[n],P[n*2+1]);
			n = n*2 + 1;
			
		}
	}
	
}

void Adaugare(int nod,int cost){
	
	H[++Q] = cost;
	P[Q] = nod;
	X[nod] = Q;
	
	Avansare(Q);
	Retrogradare(Q);
	
}

void Update(int nod,int cost){
	
	H[X[nod]] = cost;
	Avansare(X[nod]);
	Retrogradare(X[nod]);
	
}

void Delete(int n){
	
	H[1] = H[Q];
	P[1] = P[Q--];
	Avansare(n);
	Retrogradare(n);
	
}

void dijkstra(){
	
	for(int i=1;i<=N;i++){
		D[i] = inf;
		Adaugare(i,D[i]);
	}
	
	int poz = 1;
	S[poz]++;
	
	for(it = A[poz].begin(), it2 = C[poz].begin(); it < A[poz].end(); it++,it2++){
		
		D[*it] = *it2;
		Update(*it,D[*it]);
		
	}
	
	int min;
	for(int i=1; i<N; i++){
		
		min = H[1];
		poz = P[1];
		S[poz]++;
		
		for(it = A[poz].begin(), it2 = C[poz].begin(); it < A[poz].end(); it++,it2++){
			
			if(min + *it2 < D[*it]){
				D[*it] = min + *it2;
				Update(*it,D[*it]);
			}
			
		}
		
		Delete(1);
		
	}
	
}

void write(){
	
	for(int i=2;i<=N;i++){
		if(D[i]!=inf)
			printf("%d ",D[i]);
		else
			printf("0 ");
	}
	
}

int main(){
	
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	
	read();
	
	dijkstra();
	
	write();
	
	return 0;
	
}