#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define inf 20001
typedef struct neighbour {
	int name;
	int weight;
} neighbour;
typedef struct vertex {
	struct neighbour* neighbours;
	int name;
	int numNeighbours;
	int numNodes;
	int numEdges;

} vertex;
vertex* citire(FILE* f)
{
	int n, m;
	fscanf(f, "%d%d", &(n), &(m));
	vertex* graph = (vertex*)malloc((n + 1) * sizeof(vertex));
	graph->numNodes = n;
	graph->numEdges = m;
	for (int i = 1; i <= graph->numNodes; i++) {
		graph[i].name = i;
		graph[i].numNeighbours = 0;
		graph[i].neighbours = NULL;
	}
	int stanga, dreapta, value, i = 0;
	while (i < graph->numEdges) {
		fscanf(f, "%d", &stanga);
		graph[stanga].numNeighbours++;
		graph[stanga].neighbours = (neighbour*)realloc(graph[stanga].neighbours, graph[stanga].numNeighbours * sizeof(neighbour));
		fscanf(f, "%d", &dreapta);
		graph[stanga].neighbours[graph[stanga].numNeighbours - 1].name = dreapta;
		fscanf(f, "%d", &value);
		graph[stanga].neighbours[graph[stanga].numNeighbours - 1].weight = value;
		i++;
	}
	return graph;
}
int cmp(const void* a, const void* b)
{
	neighbour* A = (neighbour*)a;
	neighbour* B = (neighbour*)b;
	return (A->weight - B->weight);
}
neighbour* dijkstra(vertex* graph)
{
	neighbour* DP = (neighbour*)malloc(sizeof(neighbour) * (graph->numNodes + 1));
	int* weights = (int*)malloc(sizeof(int) * (graph->numNodes + 1));
	if (DP == NULL)
		return NULL;
	for (int i = 1; i <= graph->numNodes; i++) {
		DP[i].name = i;
		DP[i].weight = inf;
		weights[i] = inf;
	}
	DP[graph[1].name].weight = 0;
	weights[graph[1].name] = 0;
	int position = graph[1].name;
	neighbour node;
	while (DP[position].weight != inf) {
		int min = inf;
		for (int i = 1; i <= graph->numNodes; i++)
			if (weights[i] <= min) {
				min = weights[i];
				position = i;
			}
		if (min == inf)
			break;
		node = DP[position];
		for (int i = 0; i < graph[node.name].numNeighbours; i++)
			if (DP[graph[node.name].neighbours[i].name].weight > node.weight + graph[node.name].neighbours[i].weight) {
				DP[graph[node.name].neighbours[i].name].weight = node.weight + graph[node.name].neighbours[i].weight;
				weights[graph[node.name].neighbours[i].name] = DP[graph[node.name].neighbours[i].name].weight;
			}
		weights[position] = inf;
	}
	free(weights);
	return DP;
}
int main()
{
	FILE* f = fopen("dijkstra.in", "r");
	FILE* g = fopen("dijkstra.out", "w");
	vertex* Graph = citire(f);
	neighbour* Dijkstra = dijkstra(Graph);
	for (int i = 2; i <= Graph->numNodes; i++)
		fprintf(g, "%d ", Dijkstra[i].weight);
}