#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// #include "str.h"

#define MAX 100000

typedef struct graph {
int nr_nodes;
struct node** neighbours;
} graph;

typedef struct node {
int val, size, cost;
struct node* next, *head, *tail;
} node;

typedef struct HeapInfo{
    int nod, poz, d;
} HeapInfo;

void init_list_graph(graph *graph, int nodes) {
	graph->nr_nodes = nodes;
    graph->neighbours = malloc (nodes * sizeof(node *));
    for (int i = 0; i < nodes; i++) {
        graph->neighbours[i] = malloc(sizeof(node));
        graph->neighbours[i]->head = NULL;
        graph->neighbours[i]->tail = NULL;
        graph->neighbours[i]->size = 0;
    }
}

void add_nth_node(node *list, int n, int new_data, int cost) {
    node *prev, *curr;
    node *new_node;

    if (list == NULL) {
        return;
    }

    /* n >= list->size inseamna adaugarea unui nou nod la finalul listei. */
    if (n > list->size) {
        n = list->size;
    } else if (n < 0) {
        return;
    }

    curr = list->head;
    prev = NULL;
    while (n > 0) {
        prev = curr;
        curr = curr->next;
        --n;
    }

    new_node = malloc(sizeof(node));
    if (new_node == NULL) {
        perror("Not enough memory to add element!");
        exit(-1);
    }

    new_node->val = new_data;
    new_node->cost = cost;
    new_node->next = curr;
    if (prev == NULL) {
        /* Adica n == 0. */
        list->head = new_node;
    } else {
        prev->next = new_node;
    }

    if (new_node->next == NULL) {
        list->tail = new_node;
    }

    list->size++;
}

int has_edge_list_graph(graph *graph, int src, int dest) {
    int ok = 0;
    if (graph->neighbours[src] == NULL) {
        return 0;
    }
    node *current = graph->neighbours[src]->head;
    while (current != NULL) {
        int nr = current->val;
        if (nr == dest) {
            ok = 1;
            break;
        }
        current = current->next;
    }
    return ok;
}


void add_edge_list_graph(graph *graph, int src, int *dest, int cost) {
    if (graph->neighbours[src] == NULL) {
        return;
    }
    if (!has_edge_list_graph(graph, src, *dest)) {
        add_nth_node(graph->neighbours[src], graph->neighbours[src]->size, *dest, cost);
    }
}


node* get_neighbours_list_graph(graph *graph, int node) {
     if (graph->neighbours[node] == NULL) {
        return NULL;
    }
    return graph->neighbours[node];
}

node* remove_nth_node(node *list, int n) {
    node *prev, *curr;

    if (list == NULL) {
        return NULL;
    }

    if (list->head == NULL) {
        return NULL;
    }

    if (n > list->size - 1) {
        n = list->size - 1;
    } else if (n < 0) {
        return NULL;
    }

    curr = list->head;
    prev = NULL;
    while (n > 0) {
        prev = curr;
        curr = curr->next;
        --n;
    }

    if (prev == NULL) {
        list->head = curr->next;
    } else {
        prev->next = curr->next;

        if (prev->next == NULL) {
            list->tail = prev;
        }
    }

    list->size--;
    return curr;
}

int get_size(node *list) {
    if (list == NULL) {
        return -1;
    }

    return list->size;
}

void free_list(node **pp_list) {
    node *currNode;

    if (pp_list == NULL || *pp_list == NULL) {
        return;
    }

    while(get_size(*pp_list) > 0) {
        currNode = remove_nth_node(*pp_list, 0);
        free(currNode);
    }

    free(*pp_list);
    *pp_list = NULL;
}


void remove_edge_list_graph(graph *graph, int src, int dest) {
    if (graph->neighbours[src] == NULL) {
        return;
    }
    node *current = graph->neighbours[src]->head;
    int cnt = 0;
    while (current != NULL) {
        int nr = current->val;
        if (nr == dest) {
            remove_nth_node(graph->neighbours[src], cnt);
            break;
        }
        current = current->next;
        cnt++;
    }
}

void clear_list_graph(graph *graph) {
    for (int i = 0; i < graph->nr_nodes; i++) {
        free_list(&graph->neighbours[i]);
    }
    free(graph->neighbours);
}

void print_list_graph(graph *graph) {
    int v;
    for (v = 0; v < graph->nr_nodes; ++v)
    {
        node *current = graph->neighbours[v]->head;
        printf("\nVecinii lui %d\n", v);
        while (current)
        {
            printf("-> %d", current->val);
            current = current->next;
        }
        printf("\n");

    }
}


void Dijkstra(graph *graph, int source, FILE *wFile)
{
    HeapInfo h[300000];
    int size = 0;
    int d[30000], poz[300000];
    for (int i = 0; i < graph->nr_nodes; i++) {
        d[i] = MAX;
        poz[i] = -1;
    }
    d[source] = 0;
    poz[source] = size+1;
    h[poz[source]-1].nod = source;
    h[poz[source]-1].d = d[source];
    h[poz[source]-1].poz = poz[source];
    size++;
    int current = 0;
    while (current<size) {

        int nod = h[current].nod;
        node *p;
        p = graph->neighbours[nod]->head;
        while(p) {
            // printf("intru %d", p->cost);
            // printf("%d nod si vecin %d\n",nod, p->val );
            if(d[p->val] > d[nod] + p->cost) {
                // printf("ac\n");
                d[p->val] = d[nod] + p->cost;
                if(poz[p->val] == -1) {
                    // printf("aci\n");
                    poz[p->val] = size + 1;
                    h[size].nod = p->val;
                    h[size].d = d[p->val];

                    h[size].poz = poz[p->val];
                    size++;
                } else {
                    // printf("aici\n");
                    h[poz[p->val]-1].d += d[p->val];
                    }
            }
        p = p->next;
        // printf("%d  %d\n",current, size );
        }
        current++;
    }

    for (int i = 1; i < graph->nr_nodes; i++) {
        fprintf(wFile,"%d ", d[i] );
    }
}

int main() {
    int nodes, edges;
    int x[10000], y[10000], cost;
    FILE *pFile, *wFile;
    pFile = fopen("dijkstra.in", "r");
    wFile = fopen("dijkstra.out", "w");
    graph *lg = malloc(sizeof(graph));
    fscanf(pFile,"%d %d", &nodes, &edges);
    init_list_graph(lg, nodes);

    for (int i = 0; i < edges; ++i) {
        fscanf(pFile, "%d %d %d", &x[i], &y[i], &cost);
        x[i]--;
        y[i]--;
        add_edge_list_graph(lg, x[i], &y[i], cost);
        add_edge_list_graph(lg, y[i], &x[i], cost);
    }
    // printf("\nGraf cu lista de adiacenta:\n");
    // print_list_graph(lg);
    Dijkstra(lg, 0, wFile);
    // bfs_list_graph(lg, 0, dist);
    // printf("Rezultatul rularii BFS cu nodul 0\n");
    // for (int i = 0; i < lg->nr_nodes; i++) {
    // 	printf("%d are distanta %d\n", i, dist[i]);
    // }


    clear_list_graph(lg);
    free(lg);

}