#include <stdio.h>
#include <vector>
#define INF 2000000000
#define MAXN 6

using namespace std;

vector<int> G[MAXN], Cost[MAXN];
int D[MAXN], H[MAXN], poz[MAXN];
int nod,x,i,n,y,cost,m,k;

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;
	}
}

int main()
{
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	scanf("%d %d",&n,&m);
	k=n;
	for (i=1; i<=m; i++){
		scanf("%d %d %d",&x,&y,&cost);
		G[x].push_back(y);
		Cost[x].push_back(cost);
	}
	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 (i=0; i<G[x].size(); i++)
			if (D[x]+Cost[x][i]<D[G[x][i]]){
				D[G[x][i]]=D[x]+Cost[x][i];
				upheap(poz[G[x][i]]);
			}
	}
	n=k;
	for (i=2; i<=n; i++)
		printf("%d ",D[i]==INF ? 0 : D[i]);
	printf("\n");
	return 0;
}