#include<fstream>
#include<vector>
using namespace std;

#define Nr_Noduri 50010
#define inf 2000000000

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

int Poz[Nr_Noduri],D_min[Nr_Noduri];
int end,n,m;

struct heap{
	int val;
	int poz;
}Heap[Nr_Noduri];

struct nod{
	int varf;
	int dist;
};

vector<nod> L[Nr_Noduri]; 

void read(){
	
	nod nod2;
	int nod1;
	
	f>>n>>m;
	
	for(int i=1;i<=m;++i){
		f>>nod1>>nod2.varf>>nod2.dist;
		L[nod1].push_back(nod2);
	}
	
}

void initializare(){
	for(int i=1;i<=n;i++){
		Heap[++end].val=inf;
		Heap[end].poz=i;
		Poz[i]=i;
	}
	Heap[1].val=0;
}

int tata(int x){
	return x/2;
}

int left_son(int x){
	return 2*x;
}

int right_son(int x){
	return 2*x+1;
}	

void heap_down(int x){
	
	int aux2,sec;heap aux1;
	
	while(x!=end){
		if(Heap[left_son(x)].val<Heap[right_son(x)].val)
			sec=left_son(x);
		else
			sec=right_son(x);
		if(Heap[sec].val>=Heap[x].val)
			break;
		
		aux2=Poz[Heap[sec].poz];
		Poz[Heap[sec].poz]=Poz[Heap[x].poz];
		Poz[Heap[x].poz]=aux2;
		aux1=Heap[sec];
		Heap[sec]=Heap[x];
		Heap[x]=aux1;
		x=sec;
		
	}
	
	
}

void heap_up(int x){
	heap aux1;int aux2,T;
	while(Heap[T=tata(x)].val>Heap[x].val&&x!=1){
		aux2=Poz[Heap[T].poz];
		Poz[Heap[T].poz]=Poz[Heap[x].poz];
		Poz[Heap[x].poz]=aux2;
		aux1=Heap[T];
		Heap[T]=Heap[x];
		Heap[x]=aux1;
		x=T;
	}
}

void update(int x){
	heap_up(x);
	heap_down(x);
}

int pop(){
	int nod1=Heap[1].poz;
	
	D_min[nod1]=Heap[1].val;
	
	Poz[Heap[end].poz]=1;
	
	Heap[1]=Heap[end--];
	
	update(1);
	
	return nod1;
}

void update_drum(int x){
	int poz;
	for(int i=0;i<L[x].size();i++){
		poz=Poz[L[x][i].varf];
		if(Heap[poz].val>D_min[x]+L[x][i].dist){
			Heap[poz].val=D_min[x]+L[x][i].dist;
			update(poz);
		}
	}
	
}

void dijkstra(){
	
	int x;
	
	while(end!=0){
		x=pop();
		update_drum(x);
	}
	
}

void print(){
	
	for(int i=2;i<=n;i++)
		g<<D_min[i]<<" ";
	
}

int main(){
	
	read();
	
	initializare();
	
	dijkstra();
	
	for(int i=2;i<=n;i++)
		g<<D_min[i]<<" ";

	
	return 0;
}