#include <cstdio> 
#include <algorithm>
using namespace std;

#define MAX 10010


//bool used[MAX]; 
long heap[MAX],poz2[MAX],poz[MAX],n,i,x,y,c,lh,m,lung,q,z;
struct point{
	long x,cost;
	point *leg;
}*lista[MAX],*p;

long tata(long x){
	return (x-1)/2;
	if(x%2==1)return (x-1)/2;
	else return (x-2)/2;
}

void push_heap(long x) {
//	heap[++lh]=x;
	long w=x,t=tata(w),q,z;
	for(;heap[w]<heap[t] && t!=0;w=t){
		t=tata(w);q=poz[w];z=poz[t];
		swap(heap[w],heap[t]);
		swap(poz[w],poz[t]);
		swap(poz2[q],poz[z]);
	}
}
/*
 * iti scoate primul element din heap
 * se face asa:
 * - interschimbi radacina cu ultimul element (evident si scazi lungimea heapului)
 * - "adancesti" radacina cat se poate, adica compari cu
 * fiul stanga si fiul dreapta si il interschimbi cu ala mai mic (daca e mai mic decat radacina)
 *
 * pentru maxheap inlocuiesti "mai mic" cu "mai mare" evident :)
 */
long pop_heap() {
	long pozitie,q,z;
	c=poz[0];q=poz[0];z=poz[lh];
	swap(heap[0],heap[lh]);
	swap(poz[0],poz[lh]);
	swap(poz2[q],poz2[z]);
	lh--;pozitie=0;
	while(heap[pozitie]<heap[2*pozitie+1] && heap[pozitie]<heap[2*pozitie+2])
		if(heap[2*pozitie+1]<heap[2*pozitie+2]){
			q=poz[pozitie];z=poz[2*pozitie+1];
			swap(heap[pozitie],heap[2*pozitie+1]);
			swap(poz[pozitie],poz[2*pozitie+1]);
			swap(poz2[q],poz2[z]);
			pozitie=2*pozitie+1;
		}
		else{
			q=poz[pozitie];z=poz[2*pozitie+2];
			swap(heap[pozitie],heap[2*pozitie+2]);
			swap(poz[pozitie],poz[2*pozitie+2]);
			swap(poz2[q],poz2[z]);
			pozitie=2*pozitie+2;
		}
	return c;
}
int main(){
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	scanf("%ld%ld",&n,&m);
	for(i=0;i<m;i++){
		scanf("%ld%ld%ld",&x,&y,&c);
		p=new point;p->x=y;p->cost=c;p->leg=lista[x];
		lista[x]=p;
	}
	heap[0]=0;poz[0]=1;lh=0;poz2[1]=0;
	//poz[x]=y -> pe pozitia x din heap se afla dist intre nodu 1 si nodu y
	//poz2[x]=y -> distanta dintre nodu x si nodu 1 este in heap pe pozitia y
	for(p=lista[1];p!=0;p=p->leg){
		heap[++lh]=p->cost;
		poz[lh]=p->x;
		poz2[p->x]=lh;
		push_heap(lh);
	}
	x=1;
	for(i=2;i<=n;i++)
		if(poz2[i]==0){
			poz2[i]=x+lh;
			poz[x+lh]=i;
			heap[x+lh]=0x3f3f3f3f;
			x++;
		}
//	printf("%ld\n",lh);
/*	for(i=1;i<=n;i++)
		printf("%ld ",poz2[i]);
	printf("\n");*/
	while(lh>=0){
		lung=heap[0];
		long x=pop_heap();
		//used[x]=true;
		//printf("\n");
/*		for(i=0;i<n;i++)
			printf("%ld %ld    ",heap[i],poz[i]); */
		for(p=lista[x];p!=0;p=p->leg)
			if(heap[poz2[p->x]]>lung+p->cost)
				if(heap[poz2[p->x]]==0x3f3f3f3f){
					y=poz2[p->x];q=poz[y];z=poz[lh+1];
					heap[y]=lung+p->cost;
					swap(heap[y],heap[lh+1]);
					swap(poz[y],poz[lh+1]);
					swap(poz2[q],poz2[z]);
					push_heap(lh+1);
					lh++;
				}
				else{
				heap[poz2[p->x]]=lung+p->cost;
				push_heap(poz2[p->x]);
				}
		//printf("%ld %ld %ld\n",x,lung,lh);
		/*for(i=0;i<n;i++)
			printf("%ld %ld    ",heap[i],poz2[i]);
		printf("\n");*/
	}
	for(i=2;i<=n;i++)
		printf("%ld ",heap[poz2[i]]);
	printf("\n");
	fclose(stdin);
	fclose(stdout);
	return 0;
}