#define _CRT_SECURE_NO_WARNINGS

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

#define INF 1e9

typedef struct weightedGraph {
	int** weights;
	int nodes_count;
}weightedGraph;

int* distance;
int* visited;
int* parent;

int* allocate_array(int);
int** allocate_matrix(int, int);
void read_weightedGraph(weightedGraph*, const char*);
int extract_minDistance(int);
void dijkstra(weightedGraph, int, const char*);

void main(int argc, char* argv[]) {
	weightedGraph graph;
	read_weightedGraph(&graph, "dijkstra.in");
	dijkstra(graph, 0, "dijkstra.out");
}

int* allocate_array(int elements_count) {
	int* array = (int*)calloc(elements_count, sizeof(int));
	return array;
}

int** allocate_matrix(int lines, int columns) {
	int** matrix = (int**)calloc(lines, sizeof(int*));
	for (int i = 0; i < lines; i++)
		matrix[i] = (int*)calloc(columns, sizeof(int));
	return matrix;
}

void read_weightedGraph(weightedGraph* graph, const char* fileName) {
	FILE* input = fopen(fileName, "r");
	if (input == NULL) exit(1);

	int edges;
	fscanf(input, "%d %d", &graph->nodes_count, &edges);
	graph->weights = allocate_matrix(graph->nodes_count, graph->nodes_count);
	for (int i = 0, node1, node2, weight; i < edges; i++) {
		fscanf(input, "%d %d %d", &node1, &node2, &weight);
		graph->weights[node1-1][node2-1] = weight;
	}

	fclose(input);
}

int extract_minDistance(int nodes_count) {
	int Min = INT_MAX;
	int index = -1;
	for (int i = 0; i < nodes_count; i++)
		if (distance[i] < Min && !visited[i]) {
			Min = distance[i];
			index = i;
		}
	return index;
}

void dijkstra(weightedGraph graph, int source, const char* fileName) {
	distance = allocate_array(graph.nodes_count);
	visited = allocate_array(graph.nodes_count);
	parent = allocate_array(graph.nodes_count);
	for (int i = 0; i < graph.nodes_count; i++) {
		distance[i] = INF;
		visited[i] = 0;
		parent[i] = -1;
	}
	distance[source] = 0;

	for (int i = 0; i < graph.nodes_count; i++) {
		int u = extract_minDistance(graph.nodes_count);
		if (u == -1) break;
		visited[u] = 1;
		for (int v = 0; v < graph.nodes_count; v++)
			if (!visited[v] &&
				graph.weights[u][v] > 0 &&
				distance[u] + graph.weights[u][v] < distance[v]) {
				distance[v] = distance[u] + graph.weights[u][v];
				parent[v] = u;
			}
	}

	FILE* output = fopen(fileName, "w");
	for (int i = 1; i < graph.nodes_count; i++)
		fprintf(output, "%d ", distance[i]);

	fclose(output);
}