#include <stdio.h>
#define DIM 50110
#define INF 2100000000

struct nod {
	int v;
	int c;
	nod *adr;
};

nod *P[DIM], *q;

int D[DIM];
int Poz[DIM];
int H[DIM];

int n,m,x,y,c,i,min,dH;

void down(){
	int p, c, aux;
	p = 1;
	c = 2;
	while (c<=dH) {
		if (c+1<=dH && D[H[c+1]]<D[H[c]])
			c++;
		if (D[H[p]]>D[H[c]]) {
			aux = H[p];
			H[p] = H[c];
			H[c] = aux;
			
			Poz[H[p]] = p;
			Poz[H[c]] = c;
			
			p = c;
			c = 2*p;
		} else break;
	}
}

void up(int poz) {
	int c, p, aux;
	c = poz;
	p = c/2;
	while (p && D[H[p]]>D[H[c]]) {
		aux = H[p];
		H[p] = H[c];
		H[c] = aux;
		
		Poz[H[p]] = p;
		Poz[H[c]] = c;
		
		c = p;
		p = c/2;
	}
}

int main(){
	
	FILE *f = fopen("dijkstra.in","r");
	fscanf(f,"%d %d",&n, &m);
	for (i=1;i<=m;i++) {
		fscanf(f,"%d %d %d",&x, &y, &c);
		q = new nod;
		q->v = y;
		q->c = c;
		q->adr = P[x];
		P[x] = q;
	}
	fclose(f);
	
	for (i=2;i<=n;i++)
		D[i] = INF;
	D[1] = 0;
	
	H[1] = 1;
	dH = 1;
	Poz[1] = 1;
	
	while (dH) {
		min = H[1];
		H[1] = H[dH];
		Poz[H[1]] = 1;
		dH--;
		
		down();
		
		q = P[min];
		while (q) {
			if (D[min]+q->c < D[q->v]) {
				D[q->v] = D[min]+q->c;
				if (Poz[q->v] == 0) {
					dH++;
					H[dH] = q->v;
					Poz[q->v] = dH;
				}
				up(Poz[q->v]);
				down();
			}
			q = q->adr;
		}
	}
	
	FILE *g = fopen("dijkstra.out","w");
	for (i=2;i<=n;i++)
		if (D[i]==INF)
			fprintf(g,"0 ");
		else
			fprintf(g,"%d ",D[i]);
	fclose(g);
	
	return 0;
}