#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 {
    struct gnode value;
    struct node* next;
};

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

int list_add (struct node **head, struct gnode 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].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;
        tmp.v = y; tmp.cost = r;
        list_add(&graph[x], 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 = tmp->value.v;
            int adjc = 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; 
    
    fscanf(infile, "%d %d",&n,&m);
    
    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] = 0;
        fprintf(outfile, "%d ", path[i]);
    }
    fprintf(outfile, "\n");
    return 0;
}