#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define inf 1000000000

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

typedef struct nodeNDP {
    int node;
    int d;
    int parent;
} nodeNDP;

int nr_nodes,nr_edges;
graphMatrix readFile(const char* filename)
{
    graphMatrix graph;
	int i, j;
    FILE* f = fopen(filename, "r");

    fscanf(f, "%d %d", &nr_nodes, &nr_edges);
    graph.costMatrix = (int**)malloc(nr_nodes* sizeof(int*) );
    for (i = 0; i < nr_nodes; i++) {
        graph.costMatrix[i] = (int*)malloc(nr_nodes* sizeof(int));
        for (j = 0; j < nr_nodes; j++) {
            if (i == j) {
                graph.costMatrix[i][j] = 0;
                continue;
            }
            graph.costMatrix[i][j] = inf;
        }
    }

    int x, y, z;
    for (i = 0; i < nr_edges; i++) {
        fscanf(f, "%d %d %d", &x, &y, &z);
        graph.costMatrix[x - 1][y - 1] = z;
    }

    fclose(f);
    return graph;
}

nodeNDP* dijkstra(graphMatrix graph, int source)
{
    int visited[5000] = {0};

	nodeNDP* NDP = (nodeNDP*)malloc((nr_nodes + 1)*sizeof(nodeNDP));
    for (int i = 1; i <= nr_nodes; i++) {
        NDP[i].node = i;
		NDP[i].parent = -1;
        NDP[i].d = inf;
    }
    source--;
    NDP[source].d = 0;
    int counter = 1, i,min;
    while (counter <= nr_nodes - 1) {
        for (i = 0; i < nr_nodes; i++) {
            if (source != i && graph.costMatrix[source][i] != inf && visited[i] == 0) {
                int distance = NDP[source].d + graph.costMatrix[source][i];
                if (distance < NDP[i].d) {
                    NDP[i].d = distance;
                    NDP[i].parent = source;
                }
            }
        }
		counter++;
        visited[source] = 1;
        min = inf;
        for (i = 1; i <= nr_nodes; i++) {
            if (min > NDP[i].d && visited[i] == 0) {
                source = i;
			    min = NDP[i].d;
            }
        }
    }
    return NDP;
}

int main()
{
    graphMatrix graph = readFile("dijkstra.in");
    nodeNDP* NDP = dijkstra(graph, 1);
    FILE* f = fopen("dijkstra.out", "w");
    for (int i = 1; i < nr_nodes; i++) {
        if (NDP[i].d == inf) {
            fprintf(f, "%d ", 0);
        } else {
            fprintf(f, "%d ", NDP[i].d);
        }
    }
    fclose(f);

    return 0;
}