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

#define inf 999

typedef struct graphMatrix {
	int** costMatrix;
	int numNodes;
} graphMatrix;

graphMatrix initGraphMatrix(const char* filename)
{
    FILE* f = fopen(filename, "r");
	int n, m;
    fscanf(f, "%d%d", &n, &m);
    
    graphMatrix graph;
	graph.numNodes = n;
	graph.costMatrix = (int**)malloc(sizeof(int*) * (graph.numNodes + 1));
    for (int i = 1; i <= graph.numNodes; i++) {
		graph.costMatrix[i] = (int*)malloc(sizeof(int) * (graph.numNodes + 1));
		for (int j = 1; j <= graph.numNodes; j++)
			graph.costMatrix[i][j] = inf;
    }

	for(int i = 1; i <= m; i++)
    {
        int a, b, c;
        fscanf(f, "%d %d %d", &a, &b, &c);
        graph.costMatrix[a][b] = c;
    }

    fclose(f);

	return graph;
}

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);
}

void printNDP(nodeDP* NDP, int n)
{
	printf("  Node: ");
	for (int i = 1; i <= n; i++)
		printf("%5i", NDP[i].node);
	printf("\n");
	printf("     D: ");
	for (int i = 1; i <= n; i++)
		printf("%5i", NDP[i].d);
	printf("\n");
	printf("Parent: ");
	for (int i = 1; i <= n; i++)
		printf("%5i", NDP[i].parent);
	printf("\n");
}

int minDistance(nodeDP* dist, int sptSet[])
{
   
    // Initialize min value
    int min = inf;
	int min_index = -1;
 
    for (int v = 1; v < sizeof(dist) - 1; v++)
        if (sptSet[v] == 0 && dist[v].d <= min)
            min = dist[v].d, min_index = v;
 
    return min_index;
}

nodeDP* dijsktra(graphMatrix graph, int source)
{
	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;
	//TODO
	int* visited = (int*) calloc (graph.numNodes + 1, sizeof(int));

	for (int count = 1; count <= graph.numNodes - 1; count++) {
        
        int u = minDistance(NDP, visited);
 
		if(u != -1)
		{
			visited[u] = 1;
			for (int v = 1; v <= graph.numNodes; v++)
				if (!visited[v] && graph.costMatrix[u][v] && NDP[u].d != inf)
					if(NDP[u].d + graph.costMatrix[u][v] < NDP[v].d)
					{
						NDP[v].parent = u;
						NDP[v].d = NDP[u].d + graph.costMatrix[u][v];
					}
		}
	}
	//qsort(NDP, graph.numNodes, sizeof(nodeDP), cmpNDP);
	return NDP;
}

int main() //(int argc, char args[])
{
    graphMatrix graphM = initGraphMatrix("dijkstra.in");
	/*
	for(int i = 1; i <= graphM.numNodes; i++)
	{
		for(int j = 1; j <= graphM.numNodes; j++)
			printf("%d ", graphM.costMatrix[i][j]);
		printf("\n");
	}*/
    //int i = 1;
//	do{
	FILE* g = fopen("dijkstra.out", "w");
		nodeDP* NDP = dijsktra(graphM, 1);
		//printf("%d ", NDP[i].d);
		//printf("\nDijsktra rezult:\n");
		//printNDP(NDP, graphM.numNodes);
		for(int i = 2; i <= graphM.numNodes; i++)
			fprintf(g, "%d ", NDP[i].d);
		//i++;
//	}while(i < graphM.numNodes);
	fclose(g);
    return 0;
}