#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define inf 999

typedef struct graphMatrix {
	int** costMatrix;
	int numNodes;
} graphMatrix;
typedef struct nodeDP {
	int node;
	int d;
	int parent;
} nodeDP;
graphMatrix readFile(const char* filename)
{
	graphMatrix graph;
	FILE* f = fopen(filename, "r");
	int M;
	fscanf(f, "%d %d", &graph.numNodes, &M);
	graph.costMatrix = (int**)malloc(sizeof(int*) * graph.numNodes);
	int i, j;
	for (i = 0; i < graph.numNodes; i++) {
		graph.costMatrix[i] = (int*)malloc(sizeof(int) * graph.numNodes);
		for (j = 0; j < graph.numNodes; j++) {
			if (i == j) {
				graph.costMatrix[i][j] = 0;
				continue;
			}
			graph.costMatrix[i][j] = inf;
		}
	}
	int A, B, C;
	for (i = 0; i < M; i++) {
		fscanf(f, "%d %d %d", &A, &B, &C);
		graph.costMatrix[A - 1][B - 1] = C;
	}

	fclose(f);
	return graph;
}

nodeDP* dijkstra(graphMatrix graph, int source)
{
	nodeDP* NDP = (nodeDP*)malloc(sizeof(nodeDP) * (graph.numNodes + 1));
	int visited[5000] = { 0 };
	for (int i = 1; i <= graph.numNodes; i++) {
		NDP[i].node = i;
		NDP[i].d = inf;
		NDP[i].parent = -1;
	}
	source--;
	NDP[source].d = 0;
	int count = 1;
	int min;
	int i;
	while (count <= graph.numNodes - 1) {
		for (i = 0; i < graph.numNodes; i++) {
			if (source != i && graph.costMatrix[source][i] != inf && visited[i] == 0) {
				int distance = NDP[source].d + graph.costMatrix[source][i];
				if (distance < NDP[i].d) {
					NDP[i].d = distance;
					NDP[i].parent = source;
				}
			}
		}
		visited[source] = 1;
		count++;
		min = inf;
		for (i = 1; i <= graph.numNodes; i++) {
			if (min > NDP[i].d && visited[i] == 0) {
				min = NDP[i].d;
				source = i;
			}
		}
	}
	return NDP;
}
void printNDP(nodeDP* NDP, int n, graphMatrix graph)
{
	FILE* f = fopen("dijkstra.out", "w");
	for (int i = 1; i < graph.numNodes; i++) {
		if (NDP[i].d == inf) {
			fprintf(f, "%d ", 0);
		}
		else {
			fprintf(f, "%d ", NDP[i].d);
		}
	}
}

int main()
{
	graphMatrix graph = readFile("dijkstra.in");
	nodeDP* NDP = dijkstra(graph, 1);
	return 0;
}