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

}

int main() {
	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);

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

	while(q) {


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

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