#include <stdio.h>
#include <stdlib.h>

#define DIM 50010
#define INF 1e9

int n, m, x, y, cost, nHeap;
int dist[DIM], pos[DIM], heap[DIM];



void swapNodes(int a, int b){
    int aux;
    aux = heap[a];
    heap[a] = heap[b];
    heap[b] = aux;
    pos[heap[a]] = a;
    pos[heap[b]] = b;
}

void sift(int node){
    int left = 2 * node;
    int right = 2 * node + 1;
    int minNode = node;
    if(left <= nHeap && dist[heap[left]] < dist[heap[minNode]])
        minNode = left;
    if(right <= nHeap && dist[heap[right]] < dist[heap[minNode]])
        minNode = right;
    swapNodes(node, minNode);
    if(node != minNode)
        sift(minNode);
}

int percolate(int node){
    while(node > 1){
        int father = node / 2;
        if(dist[heap[father]] > dist[heap[node]]){
            swapNodes(node, father);
            node = father;
        }
        else{
            break;
        }
    }
    return node;
}

void push_heap(int node){
    heap[++nHeap] = node;
    pos[node] = nHeap;
    percolate(nHeap);
}

void pop(){
    swapNodes(1, nHeap);
    nHeap --;
    sift(1);
}

void update(int node){
    percolate(pos[node]);
}

int isHeapEmpty(){
    return (nHeap == 0);
}

int top(){
    return heap[1];
}



typedef struct edge{
    int node;
    int cost;
}Edge;

Edge make_edge(int a, int b){
    Edge aux;
    aux.node = a;
    aux.cost = b;
    return aux;
}

typedef struct ListNode{
    Edge value;
    struct ListNode *next;
}ListNode;

typedef struct List{
    int Size;
    struct ListNode *root;
}List;

List * createList(){
    List *newList = (List *)malloc(sizeof(List));
    newList->root = NULL;
    newList->Size = 0;
    return newList;
}

void addElem(List *list, Edge value){
    if(list == NULL)
        return;
    ++ list->Size;
    ListNode *newNode = (ListNode *)malloc(sizeof(ListNode));
    newNode->value = value;
    if(list->root == NULL){
        list->root = newNode;
        newNode->next = NULL;
    }
    else{
        newNode->next = list->root;
        list->root = newNode;
    }
}


void destroyList(List *list){
    if(list == NULL)
        return;
    ListNode *crtNode = list->root;
    while(crtNode != NULL){
        ListNode *aux = crtNode->next;
        free(crtNode);
        crtNode = aux;
    }
    free(list);
}



List *graf[DIM];

void initLists(int n){
    for(int i = 1; i <= n; ++ i){
        graf[i] = createList();
    }
}

void destroyLists(int n){
    for(int i = 1; i <= n; ++ i){
        destroyList(graf[i]);
    }
}

int main()
{
    FILE *in = fopen("dijkstra.in", "r");
    FILE *out = fopen("dijkstra.out", "w");

    fscanf(in, "%d %d", &n, &m);
    initLists(n);
    for(int i = 0; i < m; ++ i){
        fscanf(in, "%d %d %d", &x, &y, &cost);
        addElem(graf[x], make_edge(y, cost));
    }

    for(int i = 2; i <= n; ++ i){
        dist[i] = INF;
    }
    dist[1] = 0;
    push_heap(1);

    while(!isHeapEmpty()){
        int crtNode = top();
        pop();
        for(ListNode *nextElem = graf[crtNode]->root; nextElem != NULL; nextElem = nextElem->next){
            int nextNode = nextElem->value.node;
            int crtCost = nextElem->value.cost;

            if(dist[nextNode] > dist[crtNode] + crtCost){
                if(dist[nextNode] == INF){
                    dist[nextNode] = dist[crtNode] + crtCost;
                    push_heap(nextNode);
                }
                else{
                    dist[nextNode] = dist[crtNode] + crtCost;
                    update(nextNode);
                }
            }
        }
    }

    for(int i = 2; i <= n; ++ i){
        if(dist[i] == INF)
            dist[i] = 0;
        fprintf(out, "%d ", dist[i]);
    }


    destroyLists(n);




    return 0;
}