#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include<string.h>
#define INFIN 99999
typedef struct vertex
{
	int name;
	int parent;
	int numNeighbours;
	int d;
	struct vertex** neighbours;
	int* cost;
}vertex;
typedef struct GraphVertex
{
	int numNodes;
	int numEdges;
	struct vertex* nodes;
}GraphVertex;

typedef struct heap
{
	vertex* p[50000];
	int size;
	int count;
}heap;
GraphVertex readFile()
{
	FILE* fptr = fopen("dijkstra.in", "r");
	GraphVertex graph;
	graph.nodes = NULL;

	fscanf(fptr, "%d %d", &graph.numNodes, &graph.numEdges);
	int edges = graph.numEdges;
	graph.nodes = (vertex*)malloc(graph.numNodes * sizeof(vertex));
	for (int i = 0; i < graph.numNodes; i++)
	{
		graph.nodes[i].name = i + 1;
		graph.nodes[i].numNeighbours = 0;
		graph.nodes[i].neighbours = NULL;
		graph.nodes[i].d = INFIN;
		graph.nodes[i].parent = -1;
		graph.nodes[i].cost = NULL;
	}
	graph.nodes[0].d = 0;
	while (edges)
	{
		int left, right, cost;
		fscanf(fptr, "%d %d %d", &left, &right, &cost);
		graph.nodes[left - 1].neighbours = (vertex**)realloc(graph.nodes[left - 1].neighbours, (graph.nodes[left - 1].numNeighbours + 1) * sizeof(vertex*));
		graph.nodes[left - 1].neighbours[graph.nodes[left - 1].numNeighbours] = graph.nodes+right - 1;
		graph.nodes[left - 1].cost = (int*)realloc(graph.nodes[left - 1].cost, (graph.nodes[left - 1].numNeighbours + 1) * sizeof(int));
		graph.nodes[left - 1].cost[graph.nodes[left-1].numNeighbours] = cost;
		graph.nodes[left - 1].numNeighbours++;


		graph.nodes[right - 1].neighbours = (vertex**)realloc(graph.nodes[right - 1].neighbours, (graph.nodes[right - 1].numNeighbours + 1) * sizeof(vertex*));
		graph.nodes[right - 1].neighbours[graph.nodes[right - 1].numNeighbours] = graph.nodes+left - 1;
		graph.nodes[right - 1].cost = (int*)realloc(graph.nodes[right - 1].cost, (graph.nodes[right - 1].numNeighbours + 1) * sizeof(int));
		graph.nodes[right- 1].cost[graph.nodes[right - 1].numNeighbours] = cost;
		graph.nodes[right - 1].numNeighbours++;

		edges--;
	}

	fclose(fptr);
	return graph;
}

heap* create_heap()
{
	heap* start = (heap*)malloc(sizeof(heap));
	start->size = 1;
	start->count = 0;

	return start;
}
void up_(heap* start, int index)
{
	int parent = (index - 1) / 2;
	if (parent < 0)
		return;
	if (start->p[index]->d < start->p[parent]->d)
	{
		vertex* temp = start->p[index];
		start->p[index] = start->p[parent];
		start->p[parent] = temp;
		up_(start, parent);
	}

}
void push(heap* start, vertex* x)
{
	

	start->p[start->count] = x;
	start->count++;
	up_(start, start->count - 1);

}
void down_(heap* start, int index)
{
	if (index >= start->count)
		return;
	int left = index * 2 + 1;
	int right = index * 2 + 2;
	int lf=0, rf=0;

	int min = start->p[index]->d;
	vertex* mini = start->p[index];
	if (left<start->count && min >start->p[left]->d)
	{
		min = start->p[left]->d;
		mini = start->p[left];
		lf = 1;
	}
	if (right<start->count && min>start->p[right]->d)
	{
		min = start->p[right]->d;
		mini = start->p[right];
		lf = 0;
		rf = 1;

	}
	if (lf)
	{
		start->p[left] = start->p[index];
		start->p[index] = mini;
		down_(start, left);
	}
	if (rf)
	{
		start->p[right] = start->p[index];
		start->p[index] = mini;
		down_(start, right);
	}
}
void pop(heap* start)
{
	if (start->count == 0)
		return;

	start->count--;
	vertex* temp = start->p[start->count];
	start->p[start->count] = start->p[0];
	start->p[0] = temp;
	down_(start, 0);
}

void dijkstra(GraphVertex graph, heap* start)
{
	
	for (int i = 0; i < graph.numNodes; i++)
	{	if(graph.nodes[i].numNeighbours)
		push(start, graph.nodes + i);
	}
	while (start->count)
	{
		vertex* curr = start->p[0];
		
		for (int j = 0; j < curr->numNeighbours; j++)
			if (curr->neighbours[j]->d > curr->d + curr->cost[j])
			{
				curr->neighbours[j]->d = curr->d + curr->cost[j];
				curr->neighbours[j]->parent = curr->name;
			}
		pop(start);
	}

}
int main()
{
	GraphVertex graph = readFile();
	heap* start = create_heap();
	dijkstra(graph, start);
	FILE* out = fopen("dijkstra.out", "w");
	for (int i = 1; i < graph.numNodes; i++)
	{
	if (graph.nodes[i].d == INFIN)
			fprintf(out, "0 ");
	else
		fprintf(out, "%d ", graph.nodes[i].d);
	}
	return 0;
}