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

#define Max 65535

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

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

unsigned short int** citireMatrice(unsigned short int &colls)
{
	FILE* fin = fopen("dijkstra.in", "r");
	unsigned short int o = 0;
	fscanf(fin, "%hd %hd", &colls, &o);
	unsigned short int** matrice = (unsigned short int**)malloc(sizeof(unsigned short int*)*(colls + 1));

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

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

unsigned short int getMinList(lista* &head, lista* &min)
{
	if (!head)
	{
		lista* found = min;
		min = min->next;
		unsigned short 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, unsigned short int val, unsigned short int newDist)
{
	if (head->nodeName == val) {
		head->distance = newDist;
		return;
	}
	updateList(head->next, val, newDist);
}

void Dijkstra(unsigned short int** matrice, unsigned short int node, unsigned short int colls)
{
	lista* coada = NULL;
	unsigned short int* vizitati = (unsigned short int*)calloc(colls, sizeof(unsigned short int));
	//unsigned short int* parunsigned short inti = (unsigned short int*)malloc(colls * sizeof(unsigned short int));
	unsigned short int* distante = (unsigned short int*)malloc(colls * sizeof(unsigned short int));

	for (unsigned short int i = 0; i < colls; i++)
	{
		//if (matrice[node][i] != Max)
			//parunsigned short inti[i] = node;
		distante[i] = matrice[node][i];
	}

	append(coada, node, 0);

	while (coada)
	{
		node = getMinList(coada, coada);
		vizitati[node] = 1;
		for (unsigned short 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];
					updateList(coada, i, distante[i]);
				}
			}
		}
	}

	FILE* fout = fopen("dijkstra.out", "w");
	for (unsigned short int i = 1; i < colls; i++) {
		if (distante[i] == Max)
			fprintf(fout, "0 ");
		else
			fprintf(fout, "%hd ", distante[i]);
	}
	/*fprintf(fout, "\n");*/
	fclose(fout);
	//for (unsigned short int i = 0; i < colls; i++) {
	//	free(matrice[i]);
	//}
	//free(matrice);

}

int main()
{
	unsigned short int** matrice = NULL;
	unsigned short int colls;
	matrice = citireMatrice(colls);

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