#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#define MAX 50010
#define inf INT_MAX
struct graf{
	int nod,cost;
	struct graf *next;
};
int n,m,k;
int d[MAX],h[MAX],poz[MAX];
struct graf *a[MAX];
inline int father(int i){
	return i/2;
}
inline int left_son(int i){
	return i*2;		
}
inline int right_son(int i){
	return i*2+1;
}
void add(int where, int what, int cost){
	graf *q;//=new graf;
	q->nod=what;
	q->cost=cost;
	q->next=a[where];
	a[where]=q;
}
void scan(){
	int i,a,b,c;
    freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	scanf("%d%d",&n,&m);
	for (i=1;i<=m;++i){
		scanf("%d%d%d",&a,&b,&c);
		add(a,b,c);
	}
}
void swap(int &i,int &j){
	int aux;
	aux=i;
	i=j;
	j=aux;
}
void up_heap(int what){
	int tata;
	while (what>1){
		tata=father(what);
		if (d[h[tata]] > d[h[what]]){
			poz[h[what]]=tata;
			poz[h[tata]]=what;
			swap(h[tata],h[what]);
			what=tata;
		}
		else
			what=1;
	}
}
void down_heap(int what){
	int son;
	while (what <= k){
		son=what;
		if (left_son(what) <= k){
			son=left_son(what);
			if (right_son(what) <= k)
				if (d[h[right_son(what)]] < d[h[son]])
					son=right_son(what);
				else
					return;
			if (d[h[what]] > d[h[son]]){
				poz[h[what]]=son;
				poz[h[son]]=what;
				swap(h[what],h[son]);
				what=son;
			}
		}
		else
			return;
	}
}
void dijkstra(){
	int i;
	for (i=2; i<=n; ++i){
		d[i]=inf;
		poz[i]=-1;
	}
	poz[1]=1;
	h[++k]=1;
	while (k){
		int min=h[1];
		swap(h[1],h[k]);
		poz[h[1]]=1;
		--k;
		down_heap(1);
		graf *q=a[min];
		while (q){
			if (d[q->nod] > d[min] + q->cost){
				d[q->nod] = d[min] + q->cost;
				if (poz[q->nod] != -1)
					up_heap(poz[q->nod]);
				else{
					h[++k]=q->nod;
					poz[h[k]]=k;
					up_heap(k);
				}
			}
			q=q->next;
		}
	}
}
void print(){
	int i;
	for (i=2;i<=n;++i){
		if (d[i]==inf)
			printf("0 ");
		else
			printf("%d ",d[i]);
	}
	printf("\n");
	fclose(stdin);
	fclose(stdout);
	exit(0);
}
int main(){
	scan();
	dijkstra();
	print();
}