#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include <limits.h>
#include <stdbool.h>
#include <errno.h>

struct gnode {
    int v, cost;
};

struct node {
    void *value;
    struct node* next;
};

struct heap {
    struct gnode **arr_h;
    int* hindex;
};

int list_add (struct node **head, void* val)
{
    struct node *tmp = malloc(sizeof(struct node));
    
    tmp->value = val;
    tmp->next = *head;
    *head = tmp;
    return 0;
}

int heap_create (struct heap **heap, int n)
{
    if (heap == NULL)
        return -EINVAL;
    
    *heap = malloc (sizeof(struct heap));
    (*heap)->arr_h = malloc((n + 1) * sizeof(struct gnode*));
    (*heap)->hindex = malloc ((n + 1) * sizeof(int));
    
    for (int i = 0; i <=n; i++) {
        (*heap)->arr_h[i] = malloc (sizeof(struct gnode));
        (*heap)->arr_h[i]->v = i;
        (*heap)->arr_h[i]->cost = INT_MAX;
        (*heap)->hindex[i] = i;   
    }
    return 0;
}

int graph_init(struct node** graph, int n, int m, FILE* infile)
{  
    for (int i = 0; i <=n; i++)
        graph[i] = NULL;
    
    for(int a1 = 0; a1 < m; a1++){
        int x, y, r; 
        fscanf(infile, "%d %d %d",&x,&y,&r);
        struct gnode *tmp = malloc(sizeof(struct gnode));
        tmp->v = y; tmp->cost = r;
        list_add(&graph[x], (void*)tmp);
    }
    return 0;
}


void swap(struct heap *h, int i, int j)
{
    struct gnode* tmp = h->arr_h[i];
    h->arr_h[i] = h->arr_h[j];
    h->arr_h[j] = tmp;
    h->hindex[h->arr_h[i]->v] = i;
    h->hindex[h->arr_h[j]->v] = j;
}

int heap_remove(struct heap *heap, int *h_size, int *v, int *cost)
{
    int i = 1;
    int newmin;
    if (*h_size == 0)
        return -EINVAL;
    
    *v = heap->arr_h[1]->v;
    *cost = heap->arr_h[1]->cost;
    
    newmin = heap->arr_h[*h_size]->v;
    swap(heap, 1, *h_size);
 
    *h_size = *h_size - 1;
    
    //bubble down [0]
    while (2 * i <= *h_size) {
        int mins = heap->arr_h[2 * i]->cost;
        int j = 2*i;
        if (2*i < *h_size && heap->arr_h[2*i+1]->cost <  mins) {
            mins = heap->arr_h[2*i + 1]->cost;
            j = 2*i +1;
        }
        if (heap->arr_h[i]->cost > mins) {
            swap(heap, i, j);
            i = j;
        }  else break;         
    }

    return 0;
}

int heap_update(struct heap *heap, int h_size, int v, int newcost)
{
    // newcost can only be smaller than current cost
    //input sanitize
    int i;
    int index = heap->hindex[v];
 
    heap->arr_h[index]->cost = newcost;
    i = index;
    //bubble up
    while (i > 1) {
        if (heap->arr_h[i/2]->cost < newcost)
            break;
        swap(heap, i, i/2);
        i = i/2;            
    }

    return 0;
}

int min_paths(struct node** graph, struct heap* heap, int n, int s, int* path)
{
    int currv, currc;
    int h_size = n;

    path[s] = 0;
    heap_update(heap, h_size, s, 0);
    while (h_size != 0) {
        struct node *tmp;
        heap_remove(heap, &h_size, &currv, &currc);
        if (currc == INT_MAX)
            break;
        for (tmp = graph[currv]; tmp!=NULL; tmp= tmp->next) {
            int adjv = ((struct gnode*)tmp->value)->v;
            int adjc = ((struct gnode*)tmp->value)->cost;
            if (path[adjv] > path[currv] + adjc) {
                path[adjv] = path[currv] + adjc;
                heap_update(heap, h_size, adjv, path[currv] + adjc);
            }   
        }         
    }
    return 0;
}

int main(){
    FILE *infile, *outfile;

    infile = fopen("dijkstra.in", "r");
    outfile = fopen("dijkstra.out", "w");
    struct node **graph;
    int *path;
    struct heap *heap;
    int n, m, i, h_size; 
    
    fscanf(infile, "%d %d",&n,&m);
    h_size = n;
    
    path = malloc ((n+1) * sizeof(int));
    for (i = 0; i <=n; i++)
        path[i] = INT_MAX;
    
    graph = malloc((n+1) * sizeof(struct node*));
    graph_init(graph, n, m, infile);

    //err check
    heap_create(&heap, n);

    min_paths(graph, heap, n, 1, path);
    
    for (i = 2; i <=n; i++) {
        if (path[i] == INT_MAX)
            path[i] = -1;
        fprintf(outfile, "%d ", path[i]);
    }
    fprintf(outfile, "\n");
    return 0;
}