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

#define inf 999

int n, m;

typedef struct graphMatrix {
	int** costMatrix;
	int numNodes;
} graphMatrix;

typedef struct nodeDP {
	int node;
	int d;
	int parent;
} nodeDP;

int cmpNDP(const void* a, const void* b)
{
	nodeDP* A = (nodeDP*)a;
	nodeDP* B = (nodeDP*)b;
	return (A->d - B->d);
	/*if (A->d > B->d) return 1;
	if (A->d < B->d) return -1;*/
}
int poz(nodeDP* NDP, int val, int dim)
{
	for (int i = 1; i <= dim; i++)
		if (NDP[i].node == val)
			return i;
	return dim;
}

nodeDP* dijsktra(graphMatrix graph, int source)
{
	nodeDP* NDP = (nodeDP*)malloc(sizeof(nodeDP) * (graph.numNodes + 1));
	if (NDP == NULL)
		return NULL;
	for (int i = 1; i <= graph.numNodes; i++) {
		NDP[i].node = i;
		NDP[i].d = inf;
		NDP[i].parent = -1;
	}
	NDP[source].d = 0;
	int position = 1;
	while (position < graph.numNodes) {
		for (int i = 1; i <= graph.numNodes; i++)
			if (i != source && graph.costMatrix[source][i] != inf) {
				int src = poz(NDP, i, graph.numNodes);
				if (NDP[src].d > NDP[poz(NDP, source, graph.numNodes)].d + graph.costMatrix[source][i]) {
					NDP[src].d = NDP[poz(NDP, source, graph.numNodes)].d + graph.costMatrix[source][i];
					NDP[src].parent = source;
				}
			}
		position++;
		qsort(NDP, graph.numNodes, sizeof(nodeDP), cmpNDP);
		source = NDP[position].node;
	}
	return NDP;
}
graphMatrix citire(char* filename)
{
	FILE* f = fopen(filename, "r");
	fscanf(f, "%d %d", &n, &m);
	graphMatrix graph;
	graph.numNodes = n;
	graph.costMatrix = (int**)malloc((n + 1) * sizeof(int*));
	for (int i = 1; i <= n; i++)
		graph.costMatrix[i] = (int*)malloc((n + 1) * sizeof(int));
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			graph.costMatrix[i][j] = inf;
	int a, b, c;
	for (int i = 0; i < m; i++) {
		fscanf(f, "%d %d %d", &a, &b, &c);
		graph.costMatrix[a][b] = c;
	}
	return graph;
}

int main()
{
	graphMatrix graph = citire("dijkstra.in");
	/*for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++)
			printf("%d ", graph.costMatrix[i][j]);
		printf("\n");
	}*/
	nodeDP* NDP = dijsktra(graph, 1);
	FILE* f = fopen("dijkstra.out", "w");
	for (int i = 2; i <= n; i++) {
		/*if (NDP[i].d == inf) {
			fprintf(f, "%d ", 0);
		} else */
		{
			fprintf(f, "%d ", NDP[poz(NDP, i, n)].d);
		}
	}
	fclose(f);

	return 0;
}