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


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

} Q;

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

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

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

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

	for(int i = 1; i <= n; i++) {
		visitat[i] = -1;
		graf[i] = calloc(sizeof(int), n+1);

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




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

		fscanf(in, "%d %d %d", &nod1, &nod2, &val);
		graf[nod1][nod2] = val;
	}


	// for(int i = 1; i <= n; i++) {

	// 	for(int j = 1; j <=n; j++) {
	// 		printf("%d ", graf[i][j]);
	// 	}

	// 	printf("\n");
	// }


	Q *q = NULL;

	add_to_q(1,0,&q);
	// visitat[1] = 0;

	while(q) {


		nod_actual = q->nod;
		dist = q->dist;
		// print_q(q);
		// printf("nod_actual:%d distanta actuala:%d\n",nod_actual, dist);

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

		visitat[nod_actual] = dist;

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

			if(graf[nod_actual][i] == -1 || visitat[i] != -1) {
				continue;
			}
			add_to_q(i, graf[nod_actual][i] + dist, &q);
		}
		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++) {
		// printf("%d ", visitat[i]);

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

	// printf("\n");

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