#include <fstream>
#include <vector>

using namespace std;

ifstream in("dijkstra.in");
ofstream out("dijkstra.out");

const int N=50001;
const int M=250001;
const int INF=1<<30;

struct muchie{
	int x,cost;
}heap[N];

vector <muchie> edge[N];

int cost[N],n,m,vizitate,heapsize;

bool viz[N];

void citire(){
	muchie aux;
	int i,a,b,c;
	in>>n>>m;
	for(i=1;i<=m;i++){
		in>>a>>b>>c;
		aux.x=b;
		aux.cost=c;
		edge[a].push_back(aux);
	}
}

void schimba(int a,int b){
	heap[a].x^=heap[b].x;
	heap[b].x^=heap[a].x;
	heap[a].x^=heap[b].x;
	heap[a].cost^=heap[b].cost;
	heap[b].cost^=heap[a].cost;
	heap[a].cost^=heap[b].cost;
}

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

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

void elimin(){
	int x;
	schimba(1,heapsize);
	heapsize--;
	x=1;
	while(heap[x].cost>min(heap[2*x].cost,heap[2*x+1].cost) && 2*x+1<=heapsize){
		if(heap[2*x].cost<heap[2*x+1].cost){
			schimba(x,2*x);
			x=2*x;
		}
		else{
			schimba(x,2*x+1);
			x=2*x+1;
		}
	}
	if(heap[x].cost>heap[2*x].cost && 2*x<=heapsize){
		schimba(x,2*x);
		x=2*x;
	}
}

void Dijkstra(){
	int i,aux,nod=1,costaux;
	//viz[1]=true;
	while(vizitate!=n){
		//heapsize=0;
		for(i=0;i<edge[nod].size();++i){
			aux=edge[nod][i].x;
			costaux=edge[nod][i].cost;
			if(viz[aux])
				continue;
			heapsize++;
			if(cost[nod]+costaux<cost[aux])
				cost[aux]=cost[nod]+costaux;
			heap[heapsize].x=aux;
			heap[heapsize].cost=cost[nod]+costaux;
			urca(heapsize);
		}
		viz[nod]=true;
		vizitate++;
		while(viz[heap[1].x])
			elimin();
		nod=heap[1].x;
		elimin();
	}
}

int main(){
	citire();
	for(int i=2;i<=n;i++){
		cost[i]=INF;
	}
	Dijkstra();
	for(int i=2;i<=n;i++){
		out<<cost[i]<<" ";
	}
	return 0;
}