#include <stdio.h>
#include <stdlib.h>


typedef struct queue {
	struct queue * next;
	int nod;
	int dist;

} Q;

typedef struct muchie {
	int nod;
	int dist;
}Muchie;

typedef struct nod {
	int no_vec;
	int max_vec;
	struct muchie * vecini;
}Nod;

void add_to_q(int nod, int dist, Q ** q) {

	if(!(*q)) {
		*q = malloc(sizeof(Q));
		(*q)->next = NULL;
		(*q)->nod = nod;
		(*q)->dist = dist;
		return;
 	}

 	if((*q)->dist > dist) {
 		Q *cop = *q;
		*q = malloc(sizeof(Q));
		(*q)->next = cop;
		(*q)->nod = nod;
		(*q)->dist = dist;
		return;
 	}

 	Q *q_cop = *q;
 	Q *q_ant = *q;

	while(1) {

		if(q_cop == NULL) {
			q_cop = malloc(sizeof(Q));
			q_cop->next = NULL;
			q_cop->nod = nod;
			q_cop->dist = dist;
			q_ant->next = q_cop;
			return;
		}

		if(q_cop->dist > dist) {
			q_ant->next = malloc(sizeof(Q));
			q_ant->next->nod = nod;
			q_ant->next->dist = dist;
			q_ant->next->next = q_cop;
			return;
		}

		q_ant = q_cop;
		q_cop = q_cop -> next;
	}
}

void print_q(Q *q) {
	while(q) {
		printf("(%d,%d) ",q->nod, q->dist);
		q = q->next;
	}

	printf("\n");
}

void pop_q(Q ** q, int *nod, int *dist) {
	*dist = (*q)->dist;
	*nod = (*q)->nod;

	Q * cop = (*q);
	*q = (*q)->next;
	free(cop);
}

void print_graf (Nod *g, int n) {

	for(int i = 1; i <= n;i++) {
		for(int j = 0; j < g[i].no_vec;j++) {
			printf("%d->%d %d\n",i, g[i].vecini[j].nod,g[i].vecini[j].dist);
		}
	}

}

typedef struct heap {
	int nod;
	int dist;
} H;


void add_to_heap(H *h, int nod, int dist,int *size_heap) {
	int index = *size_heap;
	h[index].nod = nod;
	h[index].dist = dist;


	while(index != 0) {
		int parent = (index-1)/2;

		if(h[parent].dist > dist) {
			int cop_1 = h[parent].dist;
			int cop_2 = h[parent].nod;

			h[parent].dist = dist;
			h[parent].nod = nod;
			h[index].dist = cop_1;
			h[index].nod = cop_2;
			index = parent;
		} else {
			break;
		}
	}

	*size_heap = *size_heap + 1;
}

void print_heap(H *h,int size) {
	for(int i = 0; i < size; i++) {
		printf("(%d %d) ",h[i].nod,h[i].dist);
	}

	printf("\n");
}

void remove_from_heap(H *h, int *nod, int *dist, int *size_heap) {
	*nod = h[0].nod;
	*dist = h[0].dist;


	int index = 0;
	h[index].nod = h[(*size_heap)-1].nod;
	h[index].dist = h[(*size_heap)-1].dist;

	*size_heap = * size_heap - 1;

	while(index < *size_heap) {

		// print_heap(h,*size_heap);

		int left = index * 2 + 1;
		int right = index * 2 + 2;

		if(right == *size_heap) {
			right = left;
		}

		if(left >= *size_heap) {
			break;
		}

		if(h[index].dist <= h[left].dist && h[index].dist <= h[right].dist) {
			break;
		} else {
			int min = h[left].dist;
			int min_index = left;

			if(min > h[right].dist) {
				min_index = right;
			}

			int cop1, cop2;
			int cop_1 = h[min_index].dist;
			int cop_2 = h[min_index].nod;

			h[min_index].dist = h[index].dist;
			h[min_index].nod = h[index].nod;
			h[index].dist = cop_1;
			h[index].nod = cop_2;
			index = min_index;
		}
	}
}


int main() {
	int * visitat;
	int n;
	int m;
	int nod1,nod2, val, nod_actual, dist;

	H * h = malloc(sizeof(H) * 999999);
	int heap_size = 0;


	FILE *in = fopen("dijkstra.in","r");
	FILE *out = fopen("dijkstra.out", "w");
	fscanf(in, "%d %d", &n, &m);

	Nod *g = calloc(sizeof(Nod), n+1);

	visitat = calloc(sizeof(int), n+1);

	for(int i = 1; i <= n; i++) {
		visitat[i] = -1;
	}

	for(int i = 0; i < m; i++) {

		fscanf(in, "%d %d %d", &nod1, &nod2, &val);

		if(g[nod1].no_vec + 1 >= g[nod1].max_vec) {
			g[nod1].vecini = realloc(g[nod1].vecini,2 * sizeof(Muchie) * (g[nod1].no_vec+1));
			g[nod1].max_vec = 2 * (g[nod1].no_vec+1);
		}

		// g[nod1].vecini = realloc(g[nod1].vecini,sizeof(Muchie) * (g[nod1].no_vec+1));
		if(!g[nod1].vecini) {
			printf("Not allocated memory\n");
		}

		int vecin = g[nod1].no_vec;
		g[nod1].vecini[vecin].nod = nod2;
		g[nod1].vecini[vecin].dist = val;
		g[nod1].no_vec++;


	}

	Q *q = NULL;

	// add_to_q(1,0,&q);
	add_to_heap(h,1,0,&heap_size);

	// while(q) {
	while(heap_size > 0) {

		remove_from_heap(h,&nod_actual,&dist,&heap_size);
		// nod_actual = q->nod;
		// dist = q->dist;

		if(visitat[nod_actual] != -1) {
			// q = q->next;
			continue;
		}

		visitat[nod_actual] = dist;

		for(int i = 0; i < g[nod_actual].no_vec; i++) {
			int vec = g[nod_actual].vecini[i].nod;
			if(visitat[vec] != -1) {
				continue;
			}

			// add_to_q(vec, g[nod_actual].vecini[i].dist + dist, &q);
			add_to_heap(h,vec,g[nod_actual].vecini[i].dist + dist,&heap_size);
		}

		// Q * cop = q;
		// q = q->next;
		// free(cop);
	}

	if(visitat[2] == -1) {
		fprintf(out, "0");
	} else {
		fprintf(out, "%d", visitat[2]);
	}

	for(int i = 3 ; i <= n; i++) {

		if(visitat[i] == -1) {
			fprintf(out, " 0");
		} else {
			fprintf(out, " %d", visitat[i]);
		}
	}


	// for(int i = 0; i <= n; i++) {
	// 	free(graf[i]);
	// }
	free(visitat);
	// free(graf);

	fclose(in);
	fclose(out);
}