#include<stdio.h>
#include<stdlib.h>
#define INF 100000
int N,M;
int *viz,*d;
typedef struct nod {
		int val;
		int cost;
		nod *next;
	};
nod **A;
void citire() {
		int i,j,cost;
		nod *nou;
		scanf("%d ",&N);
		scanf("%d ",&M);
		A=(nod**)malloc((N+1)*sizeof(nod*));
		for(i=1;i<=N;i++)
					A[i]=NULL;
		for(i=1;i<=M;i++) {
			scanf("%d %d %d",&i,&j,&cost);
			nou=new nod;
			nou->val=j;
			nou->cost=cost;
			nou->next=A[i];
			A[i]=nou;
		}
		viz=(int*)calloc(N+1,sizeof(int));
		d=(int*)malloc((N+1)*sizeof(int));
}
void dijkstra( int x0) {
	int i,min,k,gata;
	nod *q;
	for(i=1;i<=N;i++)
				d[i]=INF;
	q=A[x0];
	while(q!=NULL) {
		d[q->val]=q->cost;
		q=q->next;
	}
	viz[x0]==1;
	gata=1;
	while(gata==1) {
		min=INF;
		for(i=1;i<=N;i++)
			if(viz[i]==0 && min >d[i]) {
				min=d[i];
				k=i;
			}
		if(min==INF) gata=0;
		if(min!=INF) {
			viz[k]=1;
			q=A[k];
			while(q!=NULL) {
				if(viz[q->val]==0 && d[q->val]>d[k]+q->cost)
						d[q->val]=d[k]+q->cost;
			q=q->next;
			}
		}
	}
	for(i=2;i<=N;i++) {
		if(d[i]==INF)
			d[i]=0;
			printf("%d ",d[i]);
	}
}
int main() {
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	citire();
	//afisare();
	dijkstra(1);
	fclose(stdin);
	fclose(stdout);
	return 0;
}