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

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

#define inf 999

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

graphMatrix initGraphMatrix(const char* filename)
{
	graphMatrix graph;
	FILE* f = fopen(filename, "r");
	if (f == NULL) {
		return;
	}
	fscanf(f, "%d", &graph.numNodes);
	fscanf(f, "%d", &graph.numEdges);
	graph.costMatrix = (int**)calloc(graph.numNodes + 1, sizeof(int*));
	for (int i = 1; i <= graph.numNodes; i++) {
		graph.costMatrix[i] = (int*)calloc(graph.numNodes + 1, sizeof(int));
	}
	int linie = 0;
	int coloana = 0;
	while (!feof(f)) {
		fscanf(f, "%d", &linie);
		fscanf(f, "%d", &coloana);
		fscanf(f, "%d", &graph.costMatrix[linie][coloana]);
	}
	for (int i = 1; i <= graph.numNodes; i++) {
		for (int j = 1; j <= graph.numNodes; j++) {
			if ((graph.costMatrix[i][j] == 0) && (i != j)) {
				graph.costMatrix[i][j] = inf;
			}
		}
	}

	return graph;
}

nodeDP* dijsktra(graphMatrix graph, int source)
{
	nodeDP* NDP = (nodeDP*)malloc(sizeof(nodeDP) * graph.numNodes);
	if (NDP == NULL)
		return NULL;
	int visited[100];
	visited[source] = 1;
	int minim = 0;
	int current = 0;
	int i, j, k;
	NDP[source].d = 0;
	for (int s = 1; s <= graph.numNodes; s++) {
		NDP[s].node = s;
		NDP[s].d = graph.costMatrix[source][s];
		NDP[s].parent = source;
		visited[s] = 0;
	}
	for (i = 1; i <= graph.numNodes - 1; i++) {
		minim = inf;
		for (j = 1; j <= graph.numNodes; j++) {
			if ((NDP[j].d < minim) && (!visited[j])) {
				minim = NDP[j].d;
				current = j;
			}
		}
		visited[current] = 1;
		for (k = 1; k <= graph.numNodes; k++) {
			if ((!visited[k]) && (minim + graph.costMatrix[current][k] < NDP[k].d)) {
				NDP[k].d = minim + graph.costMatrix[current][k];
				NDP[k].parent = current;
			}
		}
	}
	return NDP;
}

int main()
{
	graphMatrix graphM = initGraphMatrix("in.txt");
	nodeDP* NDP = dijsktra(graphM, 1);
	FILE* g = fopen("out.txt", "w");
	if (g == NULL) {
		return -1;
	}
	for (int i = 2; i <= graphM.numNodes; i++) {
		if (i == graphM.numNodes) {
			fprintf(g, "%d", NDP[i].d);
		} else {
			fprintf(g, "%d ", NDP[i].d);
		}
	}
	return 0;
}