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

#define Max 11111

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

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

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

	for (short int i = 0; i < o; i++) {
		matrice[i] = (short int*)malloc(sizeof(short int)*(o + 1));
		for (short int j = 0; j < o; j++)
		{
			matrice[i][j] = Max;
			if (i == j)
				matrice[i][i] = 0;
		}
	}
	short int a, b, c;
	for (short 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, short int val, 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);
}

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

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

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

	append(coada, node, 0);

	while (coada)
	{
		node = getMinList(coada, coada);
		vizitati[node] = 1;
		for (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 (short int i = 1; i < colls; i++) {
		if (distante[i] == Max)
			fprintf(fout, "0 ");
		else
			fprintf(fout, "%d ", distante[i]);
	}
	fprintf(fout, "\n");
	fclose(fout);
	for (short int i = 0; i < colls; i++) {
		free(matrice[i]);
	}
	free(matrice);

}

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

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