#include <stdio.h>
#include <algorithm>
#define INF 2147000000
#define MAXN 50010

using namespace std;

struct graf{
	int x,cost;
	graf *urm;
};

graf *G[MAXN], *aux;
int D[MAXN], H[MAXN], poz[MAXN];
int nod,x,i,n,y,cost,m,k,j;
char s[100];

void upheap(int nod)
{
	int tata;
	while (nod>1){
		tata=nod>>1;
		if (D[ H[tata] ]>D[ H[nod] ]){
			swap(H[tata], H[nod]);
			poz[H[tata]]=tata;
			poz[H[nod]]=nod;
			nod=tata;
		}
		else return;
	}
}

void downheap(int nod)
{
	int fiu1,fiu2,minim;
	while (nod<n){
		fiu1=nod<<1; fiu2=fiu1+1;
		minim=nod;
		if (fiu2<=n && D[H[fiu2]]<D[H[minim]])
			minim=fiu2;
		if (fiu1<=n && D[H[fiu1]]<D[H[minim]])
			minim=fiu1;
		if (D[H[minim]]<D[H[nod]]){
			swap(H[minim],H[nod]);
			poz[H[minim]]=minim;
			poz[H[nod]]=nod;
			nod=minim;
		}
		else
			return;
	}
}

void init(graf *&a)
{
	a=new graf;
	a->cost=0;
	a->x=0;
	a->urm=NULL;
}

int main()
{
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	scanf("%d %d\n",&n,&m);
	k=n;
	for (i=1; i<=m; i++){
		fgets(s,100,stdin);
		x=y=cost=j=0;
		while (s[j]!=' '){
			x=x*10+s[j]-'0';
			j++;
		}
		j++;
		while (s[j]!=' '){
			y=y*10+s[j]-'0';
			j++;
		}
		j++;
		while (s[j]!=10){
			cost=cost*10+s[j]-'0';
			j++;
		}
		init(aux);
		aux->urm=G[x];
		aux->cost=cost;
		aux->x=y;
		G[x]=aux;
	}
	for (i=1; i<=n; i++){
		D[i]=INF;
		H[i]=i;
		poz[i]=i;
	}
	D[1]=0; 
	while (n){
		x=H[1];
		swap(H[1],H[n]);
		poz[H[1]]=1; poz[H[n]]=n;
		n--;
		downheap(1);
		for (aux=G[x]; aux; aux=aux->urm)
			if (D[x]+aux->cost < D[aux->x]){
				D[aux->x]=D[x]+aux->cost;
				upheap(poz[aux->x]);
			}
	}
	n=k;
	for (i=2; i<=n; i++)
		printf("%d ",D[i]==INF ? 0 : D[i]);
	printf("\n");
	return 0;
}