#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include <string.h>
#include <time.h>
#include <ctype.h>

#define Max 111111111

typedef struct lista {
	int nodeName;
	int distance;
	lista* next;
} lista;

//int** citireMatrice(char* filename, int &colls)
//{
//	FILE* fin = fopen(filename, "r");
//	fscanf(fin, "%d", &colls);
//	int** matrice = (int**)malloc(sizeof(int*)*(colls + 1));
//	for (int i = 0; i < colls; i++)
//	{
//		matrice[i] = (int*)malloc(sizeof(int)*(colls + 1));
//		for (int j = 0; j < colls; j++)
//		{
//			fscanf(fin, "%d", &matrice[i][j]);
//		}
//	}
//	fclose(fin);
//	return matrice;
//}

int** citireMatrice(char* filename, int &colls)
{
	FILE* fin = fopen(filename, "r");
	int o = 0;
	fscanf(fin, "%d %d", &colls, &o);
	int** matrice = (int**)malloc(sizeof(int*)*(o + 1));

	for (int i = 0; i < o; i++) {
		matrice[i] = (int*)malloc(sizeof(int)*(o + 1));
		for (int j = 0; j < o; j++)
		{
			matrice[i][j] = Max;
			if (i == j)
				matrice[i][i] = 0;
		}
	}
	int a, b, c;
	for (int i = 0; i < o; i++)
	{
		fscanf(fin, "%d %d %d", &a, &b, &c);
		matrice[a - 1][b - 1] = c;
	}
	fclose(fin);
	return matrice;
}

void append(lista* &head, int val, int distance)
{
	if (!head)
	{
		head = (lista*)malloc(sizeof(lista));
		head->distance = distance;
		head->next = NULL;
		head->nodeName = val;
		return;
	}
	append(head->next, val, distance);
}

int getMinList(lista* &head, lista* &min)
{
	if (!head)
	{
		lista* found = min;
		min = min->next;
		int ret = found->nodeName;
		free(found);
		return ret;
	}
	if (head->distance < min->distance)
		return getMinList(head->next, head);
	else
		return getMinList(head->next, min);
}

void updateList(lista* head, int val, int newDist)
{
	if (head->nodeName == val) {
		head->distance = newDist;
		return;
	}
	updateList(head->next, val, newDist);
}

void Dijkstra(int** matrice, int node, int colls)
{
	lista* coada = NULL;
	int* vizitati = (int*)calloc(colls, sizeof(int));
	int* parinti = (int*)malloc(colls * sizeof(int));
	int* distante = (int*)malloc(colls * sizeof(int));

	for (int i = 0; i < colls; i++)
	{
		if (matrice[node][i] != Max)
			parinti[i] = node;
		distante[i] = matrice[node][i];
	}

	append(coada, node, 0);

	while (coada)
	{
		node = getMinList(coada, coada);
		vizitati[node] = 1;
		for (int i = 0; i < colls; i++)
		{
			if (matrice[node][i] != 0 && matrice[node][i] != Max && vizitati[i] == 0)
			{
				append(coada, i, distante[i]);
				if (distante[node] + matrice[node][i] < distante[i])
				{
					distante[i] = distante[node] + matrice[node][i];
					parinti[i] = node;
					updateList(coada, i, distante[i]);
				}
			}
		}
	}
	char* filename = _strdup("dijkstra.out");
	FILE* fout = fopen(filename, "w");
	for (int i = 1; i < colls; i++)
		fprintf(fout, "%d ", distante[i]);
	printf("\n");
	fclose(fout);
}

int main()
{
	int** matrice = NULL;
	char* filename = _strdup("dijkstra.in");
	int colls;
	matrice = citireMatrice(filename, colls);

	Dijkstra(matrice, 0, colls);
	_getch();
	return 0;
}