#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

#define Nmax 50001

#define INF 0x3f3f3f3f

int D[Nmax], H[Nmax], poz[Nmax], N, M, L;

struct graf {
	int nod, cost;
	graf *next; 
} *G[Nmax];

void add(int where, int nod, int cost) {
	graf *p;
	p=new graf;
	p->nod=nod;
	p->cost=cost;
	p->next=G[where];
	G[where]=p;
}

void Heap_Down(int k) {
	int son=k;
	if(2*k<=L && D[H[2*k]]<D[H[son]])
		son=k;
	if(2*k+1<=L && D[H[2*k+1]]<D[H[son]])
		son=k;
	if(son!=k) {
		swap(H[k],H[son]);
		poz[H[k]]=son;
		poz[H[son]]=k;
		Heap_Down(son);
	}
}

void Heap_Up(int k) {
	while(k>1 && D[H[k]]<D[H[k/2]]) {
		swap(H[k],H[k/2]);
		poz[H[k]]=k/2;
		poz[H[k/2]]=k;
		k/=2;
	}
}

void insert(int val) {
	H[++L]=val;
	poz[H[L]]=L;
	Heap_Up(L);
}

void erase(int k) {
	H[k]=H[L];
	L--;
	Heap_Down(L);
}

int main() {
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	
	int i, x, y, z, min;
	graf *p;
	scanf("%d %d",&N,&M);
	while(M--) {
		scanf("%d %d %d",&x,&y,&z);
		add(x,y,z);
	}
	
	memset(D,INF,sizeof(D));
	memset(poz,-1,sizeof(poz));
	insert(1); D[1]=0;
	while(L) {
		min=H[1];
		erase(1);
		for(p=G[min]; p; p=p->next) 
			if(D[p->nod]>D[min]+p->cost) {
				D[p->nod]=D[min]+p->cost;
				if(poz[p->nod]!=-1) 
					Heap_Up(p->nod);
				else 
					insert(p->nod);
			}
	}
	
	for(i=2; i<=N; i++)
        printf("%d ",D[i] == INF ? 0 : D[i]);
	printf("\n");
	
	return 0;
}