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

#define inf 20001 

typedef struct graph {
	int** matrix;
	int numNodes;
	int numEdges;
}graph;

typedef struct list {
	int node;
	int weight;
} list;

typedef struct nodeDP {
	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);
}

int cmpList(const void* a, const void* b)
{
	list* A = (list*)a;
	list* B = (list*)b;
	return (A->weight - B->weight);
}

list priorityQueue[100];
int queueIndex = 0;

void push(int node_src, int weight_src)
{
	list element;
	element.node = node_src;
	element.weight = weight_src;
	if (queueIndex < 100)
		priorityQueue[queueIndex++] = element;
	else
		return;
}

int pop()
{
	int aux = priorityQueue[0].node;
	for (int i = 0; i < queueIndex - 1; i++)
		priorityQueue[i] = priorityQueue[i + 1];
	queueIndex--;
	return aux;
}

graph readGraph(const char* filename) {
	FILE* f = fopen(filename, "r");
	graph newGraph;

	if (!f)
		return;
	fscanf(f, "%d %d\n", &newGraph.numNodes, &newGraph.numEdges);

	newGraph.numNodes++;

	newGraph.matrix = (int**)malloc(sizeof(int*) * newGraph.numNodes);
	for (int i = 0; i < newGraph.numNodes; i++)
		newGraph.matrix[i] = (int*)malloc(sizeof(int) * newGraph.numNodes);

	for (int i = 0; i < newGraph.numNodes; i++) {
		for (int j = 0; j < newGraph.numNodes; j++)
			newGraph.matrix[i][j] = inf;
		newGraph.matrix[i][i] = 0;
	}

	int aux_i, aux_j, cost;

	for (int i = 0; i < newGraph.numEdges; i++) {
		fscanf(f, "%d %d %d\n", &aux_i, &aux_j, &cost);
		newGraph.matrix[aux_i][aux_j] = cost;
	}

	fclose(f);

	return newGraph;
}

void dijkstra(graph graph_src) {

	nodeDP* NDP = (nodeDP*)malloc(sizeof(nodeDP) * graph_src.numNodes);

	for (int i = 0; i < graph_src.numNodes; i++) {
		NDP[i].d = inf;
		NDP[i].parent = -1;
	}

	push(1, 0);

	int visited[100] = { 0 };

	while (queueIndex != 0) {
		for (int i = 0; i < graph_src.numNodes; i++)
			if (!visited[i] && graph_src.matrix[priorityQueue[0].node][i] != 0 && graph_src.matrix[priorityQueue[0].node][i] != inf) {
				push(i, graph_src.matrix[priorityQueue[0].node][i]);
				if (NDP[priorityQueue[0].node].parent == -1) {
					NDP[i].d = graph_src.matrix[priorityQueue[0].node][i];
					NDP[i].parent = priorityQueue[0].node;
				}
				else if (NDP[i].d > graph_src.matrix[priorityQueue[0].node][i] + NDP[priorityQueue[0].node].d) {
					NDP[i].d = graph_src.matrix[priorityQueue[0].node][i] + NDP[priorityQueue[0].node].d;
					NDP[i].parent = priorityQueue[0].node;
				}
			}
		visited[pop()] = 1;
		qsort(priorityQueue, queueIndex, sizeof(list), cmpList);
	}

	FILE* out = fopen("dijkstra.out", "w");

	for (int i = 2; i < graph_src.numNodes; i++) {
		if (NDP[i].d == inf)
			fprintf(out, "%d ", 0);
		else
			fprintf(out, "%d ", NDP[i].d);
	}

	fclose(out);
}

int main() {
	graph newGraph = readGraph("dijkstra.in");

	dijkstra(newGraph);

	return 0;
}