#include <stdio.h>
#include <stdlib.h>
#define INT_MAX 1<<15

typedef struct binary_heap{
    int n;//nr maxim de elemente
    int curr;//numar curent de elemente
    int *heap;
    int *map;
} binary_heap;
void swap(int *a, int *b);
int parent(int i);
int left(int i);
int right(int i);
binary_heap *create_heap(int max);
void add_to_binary_heap(binary_heap *h, int x, int *d);
int remove_from_binary_heap(binary_heap *h, int *d);
void print_array(int *array, int n);
void increase_priority(binary_heap *h, int x, int *d);

typedef struct node{
    int nod;
    int cost;  
    struct node *next;
} node;

typedef struct graf{
    int n;//nr de noduri
    node **adj;
} graf;

node *new_list(int nod, int cost);
void free_list(node **l);
void add_node(node **l, int nod, int cost);
graf *create_graf(int nodes);
void add_edge(graf *g, int nod1, int nod2, int cost);
void print_graf(graf *g);
void collapse_graf(graf *g);
void swap(int *a, int *b)
{
    int aux = *a;
    *a = *b;
    *b = aux;
}

//implementare minheap

int parent(int i)
{
    return (i-1)/2;
}

int left(int i) 
{ 
    return (2*i + 1);
}

int right(int i) 
{ 
    return (2*i + 2);
}

binary_heap *create_heap(int max)
{
    binary_heap *h = malloc(sizeof(binary_heap));
    h->n = max;
    h->curr = 0;
    h->heap = malloc(max * sizeof(int));
    h->map = malloc(max * sizeof(int));
    return h;
}

void add_to_binary_heap(binary_heap *h, int x, int *d)
{
    (h->curr)++;//incrementez valoarea nr curent de elem
    h->heap[(h->curr) - 1] = x;//pun la final x

    int cpos = h->curr - 1;//pozitia curenta din vector,
    h->map[x] = cpos;
    //inainte de cernere
    while(cpos && d[h->heap[parent(cpos)]] > d[h->heap[cpos]]) {
        swap(&h->heap[parent(cpos)], &h->heap[cpos]);
        swap(h->map + parent(cpos), h->map + cpos);
        cpos = parent(cpos);
    }
}

int remove_from_binary_heap(binary_heap *h, int *d)
{
    int out = h->heap[0];
    h->map[out] = 0;
    swap(h->heap, h->heap + h->curr - 1);
    (h->curr)--;

    int cpos = 0;//pozitia curenta inainte de cernere

    while(cpos < h->curr && (d[h->heap[left(cpos)]] < d[h->heap[cpos]] || d[h->heap[right(cpos)]] < d[h->heap[cpos]])){
        if(d[h->heap[left(cpos)]] > d[h->heap[right(cpos)]] && right(cpos) < h->curr) {
            swap(&h->heap[right(cpos)], &h->heap[cpos]);
            swap(h->map + right(cpos), h->map + cpos);
            cpos = right(cpos);
            continue;
        }
        if(left(cpos) < h->curr) {
        swap(&h->heap[left(cpos)], &h->heap[cpos]);
        swap(h->map + left(cpos), h->map + cpos);
        cpos = left(cpos);
        continue;
        }
        break;
    }

    return out;
}

void print_array(int *array, int n)
{
    for(int i = 0; i < n; i++)
        printf("%d\n", array[i]);
}

//ia un element din heap si ii updateaza prioritatea
//in timpul algoritmului dijkstra modific uneori 
//un element si pentru ca e deja in heap, prioritatea
//nu i se schimba
void increase_priority(binary_heap *h, int x, int *d)
{
    int cpos = x;
    while(cpos && d[h->heap[parent(cpos)]] > d[h->heap[cpos]]) {
        swap(&h->heap[parent(cpos)], &h->heap[cpos]);
        swap(h->map + parent(cpos), h->map + cpos);
        cpos = parent(cpos);
    }
}
//implementarea grafului foloseste liste
//de adiacenta
//restul functiilor sunt cunoscute, folosite
//in teme si in laboratoare
node *new_list(int nod, int cost)
{
    node *l = malloc(sizeof(node));
    l->nod = nod;
    l->cost = cost;
    l->next = NULL;
    return l;
}

void free_list(node **l)
{
    node *p = *l;
    while(p != NULL)
    {
        p = (*l)->next;
        free(*l);
        *l = p;
    }
}

void add_node(node **l, int nod, int cost)
{
    if((*l) == NULL) {
        (*l) = new_list(nod, cost);
        return;
    }

    node *new = new_list(nod, cost);
    new->next = (*l);
    *l = new;
}


graf *create_graf(int nodes)
{
    graf *g = malloc(sizeof(graf));
    g->n = nodes;
    g->adj = calloc(nodes, sizeof(node *));

    return g;
}

void add_edge(graf *g, int nod1, int nod2, int cost) 
{
    add_node(g->adj + nod1, nod2, cost);
}

void print_graf(graf *g)
{
    for(int i = 0; i < g->n; i++)
    {
        printf("vecinii lui %d:\n", i);
        node *p = g->adj[i];//pentru ca am dat calloc
        //ele sunt initializate cu 0, deci daca nodul nu exista
        //p e null
        while(p != NULL) {
            printf("%d %d\n", p->nod, p->cost);
            p = p->next;
        }
    }
}

void collapse_graf(graf *g)
{
    for(int i = 0; i < g->n; i++)
        free_list(g->adj + i);
    free(g->adj);
    free(g);
}


//algoritmul dijksta
int *dijkstra(graf *g, int source)
{
    int *d = malloc(g->n * sizeof(int));
    int *viz = calloc(g->n * sizeof(int), 1);
    //int *heappos = calloc(g->n * sizeof(int), 1);//pozitia in heap
    //a fiecarui nod
    for(int i = 0; i < g->n; i++)
        d[i] = INT_MAX;
    d[source] = 0;
    viz[source] = 1;

    binary_heap *h = create_heap(g->n);
    add_to_binary_heap(h, source, d);

    while(h->curr != 0) {
        int current = remove_from_binary_heap(h, d);
        viz[current] = 0;
        node *p = g->adj[current];

        while(p != NULL) {
            int neigh = p->nod;
            int cost = p->cost;

            if(d[neigh] > d[current] + cost) {
                d[neigh] = d[current] + cost;
                if(!viz[neigh]) {
                    viz[neigh] = 1;
                    add_to_binary_heap(h, neigh, d);
                }
                else {
                    increase_priority(h, h->map[neigh], d);
                }
            }
            p = p->next;
        }
    }
    free(h->heap);
    free(h->map);
    free(h);
    free(viz);
    return d;
}

int main(void)
{
    int n, m;
    FILE *in = fopen("dijkstra.in", "r");
    FILE *out = fopen("dijkstra.out", "w");
    fscanf(in, "%d%d", &n, &m);
    graf *g = create_graf(n + 1);

    for(int i = 0; i < m; i++) {
        int x, y, cost;
        fscanf(in, "%d%d%d", &x, &y, &cost);
        add_edge(g, x, y, cost);
    }
    int *d = dijkstra(g, 1);
    for(int i = 2; i <= n; i++)
        fprintf(out, "%d ", d[i]);
    free(d);
    fclose(in);
    fclose(out);
    collapse_graf(g);
}