#include<stdio.h>
#include<vector>
#include<algorithm>
#define NMAX 100001
#define MMAX 2500003

using namespace std;

const int inf=1<<30;

struct lista{
	int x;
	int cost;
};

vector <lista> graf[50005]; 
int cost[NMAX];
int nr_vf, muchii,lh;
int heap[NMAX],poz[NMAX];

void inter(int a,int b){
	int x,y;
	x=heap[a];
	y=heap[b];
	heap[a]^=heap[b];
	heap[b]^=heap[a];
	heap[a]^=heap[b];
	poz[x]^=poz[y];
	poz[y]^=poz[x];
	poz[x]^=poz[y];

}

inline int min(int a,int b){
return a<b? a : b;
}

void pop(){
	int x;
	inter(1,lh);
	lh--;
	x=1;
	while(cost[heap[x]]>min(cost[heap[2*x]],cost[heap[2*x+1]])&&2*x+1<=lh){
	if(cost[heap[2*x]]<cost[heap[2*x+1]]){
		inter(x,2*x);
		x=2*x;
	}
	else{
		inter(x,2*x+1);
		x=2*x+1;
	}
	}
	
	if(cost[heap[x]]<cost[heap[2*x]]&& 2*x<=lh){
		inter(x,2*x);
		x=2*x;
	}
}

void add(int x){
	while(x>1){
		if(cost[heap[x]]<cost[heap[x/2]]){
			inter(x,x/2);
			x=x/2;
		}
		else
			break;
	}
}

void dijkstra_heap(){
	for(int i=2;i<=nr_vf;i++)
		cost[i]=inf;
	
	int viz=0;
	int j=1;
	
	while(viz<nr_vf){
		for(unsigned int i=0; i<graf[j].size();i++){
			int nod=graf[j][i].x;
			int cost_nod=graf[j][i].cost;
			if(poz[nod]==-1)
				continue;
				if(cost[nod]==inf){
					lh++;
					cost[nod]=cost[j]+cost_nod;
					heap[lh]=nod;
					poz[nod]=lh;
					add(lh);
					continue;
				}
				if(cost[j]+cost_nod<cost[nod]){
					cost[nod]=cost[j]+cost_nod;
					add(poz[nod]);
				}
		}
		poz[j]=-1;
	viz++;
	j=heap[1];
	pop();
	}
}

	

int main(){
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	scanf("%d%d", &nr_vf, &muchii);
	int a,b,c;
	lista aux;
	for(int i=1;i<=muchii;i++){
		scanf("%d%d%d", &a,&b, &c);
		aux.x=b;
		aux.cost=c;
		graf[a].push_back(aux);
	}

	dijkstra_heap();
	for(int i=2;i<=nr_vf;i++){
		if(cost[i]==inf)
			printf("0 ");
		else 
			printf("%d ", cost[i]);
		
	}
  
  return 0;
}