#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define inf 20010

typedef struct graphMatrix {
	int** costMatrix;
	int numNodes;
} graphMatrix;
typedef struct nodeDP {
	int node;
	int d;
	int parent;
} nodeDP;

int cmpNDP(const void* a, const void* b)
{
	nodeDP* A = (nodeDP*)a;
	nodeDP* B = (nodeDP*)b;
	return (A->d - B->d);
}
nodeDP* dijsktra(graphMatrix graph, int source)
{
	int nod_curent;
	nodeDP* NDP = (nodeDP*)malloc(sizeof(nodeDP) * graph.numNodes);
	if (NDP == NULL)
		return NULL;
	for (int i = 1; i <= graph.numNodes; i++) {
		NDP[i].node = i;
		NDP[i].d = inf;
		NDP[i].parent = -1;
	}
	NDP[source].d = 0;
	int position = 1;
	while (position != (graph.numNodes + 1)) {
		qsort(NDP, graph.numNodes, sizeof(nodeDP), cmpNDP);
		nod_curent = NDP[position].node;
		for (int i = 1; i <= graph.numNodes; i++)
			if ((graph.costMatrix[nod_curent][NDP[i].node] != inf) && (NDP[i].node != nod_curent)) {
				if (NDP[position].d + graph.costMatrix[nod_curent][NDP[i].node] < NDP[i].d) {
					NDP[i].d = NDP[position].d + graph.costMatrix[nod_curent][NDP[i].node];
					NDP[i].parent = NDP[position].node;
				}
			}
		position++;
	}
	return NDP;
}

graphMatrix construieste(const char* nume)
{
	int n, m;
	int a, b, c;
	graphMatrix matrice;
	FILE* f = fopen(nume, "r");
	fscanf(f, "%d %d\n", &n, &m);
	matrice.numNodes = n;
	matrice.costMatrix = (int**)malloc(sizeof(int*) * n);
	for (int i = 1; i <= n; i++) {
		matrice.costMatrix[i] = (int*)malloc(sizeof(int) * n);
	}
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++) {
			if (i == j)
				matrice.costMatrix[i][j] = 0;
			else
				matrice.costMatrix[i][j] = inf;
		}
	for (int i = 1; i <= m; i++) {
		fscanf(f, "%d %d %d\n", &a, &b, &c);
		matrice.costMatrix[a][b] = c;
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++)
			printf("%d ", matrice.costMatrix[i][j]);
		printf("\n");
	}
	//fclose(f);
	return matrice;
}
int cmpNDP2(const void* a, const void* b)
{
	nodeDP* A = (nodeDP*)a;
	nodeDP* B = (nodeDP*)b;
	return (A->node - B->node);
}
void print_dijsktra(nodeDP* NDP, int nr_noduri)
{
	FILE* fout = fopen("dijkstra.out", "w");
	qsort(NDP, nr_noduri, sizeof(nodeDP), cmpNDP2);
	for (int i = 2; i <= nr_noduri; i++) {
		if (NDP[i].d == inf)
			fprintf(fout, "%d ", 0);
		else
			fprintf(fout, "%d ", NDP[i].d);

		//fclose(fout);
	}
}
int main()
{
	graphMatrix graph = construieste("dijkstra.in");
	nodeDP* NDP = dijsktra(graph, 1);
	print_dijsktra(NDP, graph.numNodes);
	return 0;
}