#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;

} 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;
	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 < m) {
		fscanf(f, "%d%d%d", &stanga, &dreapta, &value);
		graph[stanga].numNeighbours++;
		graph[stanga].neighbours = (neighbour*)realloc(graph[stanga].neighbours, graph[stanga].numNeighbours * sizeof(neighbour));
		graph[stanga].neighbours[graph[stanga].numNeighbours - 1].name = dreapta;
		graph[stanga].neighbours[graph[stanga].numNeighbours - 1].weight = value;
		i++;
	}
	return graph;
}
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[1].weight = 0;
	weights[1] = 0;
	int position = 1;
	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;
	}
	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)
		(Dijkstra[i].weight < inf) ? fprintf(g, "%d ", Dijkstra[i].weight) : fprintf(g, "0 ");
	fclose(f);
	fclose(g);
	return 0;
}