#include <cstdio>
using namespace std;
#define MAX 50010
#define INFINIT 2000000000
struct muchie{
	int capat, cost;
	muchie * next;
};

muchie *a[MAX]; // listele de adiacenta
int d[MAX], // vectorul cu distantele de la 1 la i
	v[MAX], // vectorul de vizitati
	H[MAX], nH, // heapul cu nodurile grafului, pentru alegerea nodului curent si dimensiunea lui
	vpoz[MAX], //vectorul cu pozitia fiecarui nod in heap;
	n; // numarul de noduri
	
void read(){
	int m,i,j,cost;
	scanf("%d%d", &n, &m);
	muchie *p;
	for(i=1;i<=n;++i)
		a[i]=NULL;
	for( ; m ; --m){
		scanf("%d%d%d", &i, &j, &cost);
		p=new muchie;
		p->capat = j;
		p->cost = cost;
		p->next = a[i];
		a[i] = p;
	}
}

void write(){
	freopen("dijkstra.out","w",stdout);
	for(int i=2;i<=n;i++)
		printf("%d ",d[i]==INFINIT?0:d[i]);
	
}
void stergeDinHeap(int indice){
	//sterg din heap elementul de indice precizat
	H[indice] = H[nH--];
	vpoz[H[indice]]=indice;
	int esteHeap = 0, i=indice, k, aux;
	while(!esteHeap  && 2*i<=nH){
		k = 2*i;
		if(k+1<=nH && d[H[k]]>d[H[k+1]])
			k++;
		if(d[H[k]]>=d[H[i]])
			esteHeap = 1;
		else{
			aux= H[i]; H[i]=H[k]; H[k]=aux;
			vpoz[H[i]]=i;
			vpoz[H[k]]=k;
			i=k;
		}
	}
}

void muta_sus(int indice){
	//muta in heap in sus elementul de indice dat
	int esteHeap = 0, i=indice , aux;
	while(!esteHeap && i/2>0)
		if(d[H[i]] >= d[H[i/2]])
			esteHeap =1;
		else{
			aux = H[i]; H[i] = H[i/2]; H[i/2] = aux;
			vpoz[H[i]] = i;
			vpoz[H[i/2]] = i/2;
			i/=2;
		}
}

void dijkstra(int start){
	nH=n;
	for(int i=1;i<=n;i++){
		H[i]=i; 		vpoz[i]=i;
		d[i]=INFINIT; 	v[i]=0;		
	}
	v[start]=1;	d[start]=0;
	stergeDinHeap(start);
	muchie *p;
	for(p=a[start]; p ;p = p->next){
		d[p->capat] = p->cost;
		muta_sus(vpoz[p->capat]);
	}
	int poz;
	for(int ll=1;ll<n; ++ll){
		poz = H[1];
		stergeDinHeap(1);
		if(d[poz]==INFINIT)
			break;
		v[poz] = 1;
		for(p = a[poz]; p ;p = p->next)
			if(!v[p->capat] && d[p->capat] > d[poz] + p->cost){
				d[p->capat] = d[poz] + p->cost;
				muta_sus(vpoz[p->capat]);
			}
	}
}

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