#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <string>
#include <vector>

#define maxN 50005
#define maxM 250005
#define INF 90000000
using namespace std;

typedef pair<int, int> nodAndCost;

int N, M, c, x, y, heapSize;
vector<nodAndCost > arr[maxN];
nodAndCost minHeap[maxN];
vector<int> cost(maxN, INF), vizitat(maxN, 0), isInHeap(maxN, 0);
int pozInHeap[maxN];

int father(int nod) {
    return nod / 2;
}

int rightSon(int nod) {
    return 2 * nod + 1;
}

int leftSon(int nod) {
    return 2 * nod;
}

nodAndCost minimumValue() {
    return minHeap[1];
}

void swapV(int a, int b) {
    nodAndCost auxF = minHeap[a];
    minHeap[a] = minHeap[b];
    minHeap[b] = auxF;

    int aux = pozInHeap[minHeap[a].first];
    pozInHeap[minHeap[a].first] = pozInHeap[minHeap[b].first];
    pozInHeap[minHeap[b].first] = aux;
}

void down_heap(int k) {
    int son, sonR, sonL;
    do {
        son = 0;
        sonL = leftSon(k);
        if(sonL <= heapSize) {//pentru ca sa nu ieie si frunzele (adica ele nu au fii) si oricum ele in heap sunt deja asezate
                // nu exista pos. ca mai jos de ele sa fie ceva cu o valoare mai mare decat ele caci nu exista nimic
            son = sonL;
            sonR = rightSon(k);
            if (sonR <= heapSize && minHeap[sonR].second < minHeap[sonL].second) {
                son = sonR;
            }
            if (minHeap[son].second >= minHeap[k].second) {
                son = 0;
            }
        }
        if(son) {
            swapV(son, k);
            k = son;
        }
    }while(son);
}

void up_heap(int k) {
    while(k > 1 && minHeap[k].second < minHeap[father(k)].second) {
        swapV(k, father(k));
        k = father(k);
    }
}

void cutAnElement(int k) {
    isInHeap[minHeap[1].first] = 0;
    swapV(k, heapSize);
    --heapSize;
    down_heap(k);
}

void insertAnElement(nodAndCost key) {
    if(!isInHeap[key.first]) {
        minHeap[++heapSize] = key;
        pozInHeap[key.first] = heapSize;
        isInHeap[key.first] = 1;
        up_heap(heapSize);
    } else { // in this case update the cost, the node already exists in heap
        minHeap[pozInHeap[key.first]].second = key.second;
        up_heap(pozInHeap[key.first]);
    }
}

void buildHeap() {
    for(int i = heapSize / 2; i >= 1; --i)
        down_heap(i);
}

void sortHeap() {
    buildHeap();
    for(int i = heapSize; i >= 2; --i) {
        swapV(i, 1);
        --heapSize;
        down_heap(1);
    }
}

void citireMuchii() {
    for(int i = 1; i <= M; ++i) {
        scanf("%d %d %d", &x, &y, &c);
        arr[x].push_back(make_pair(y, c));
    }
}
void afisareMuchii() {
    for(int i = 1; i <= N; ++i) {
        printf("%d: ", i);
        for(int j = 0; (unsigned)j < arr[i].size(); ++j) {
            printf(" %d, c = %d ", arr[i][j].first, arr[i][j].second);
        }
        printf("\n");
    }
}

void dijkstra_heap(int start) {
    int pminA, pminC, calcActual;
    nodAndCost m;
    cost[start] = 0;
    insertAnElement(make_pair(start, cost[start]));
    while(heapSize > 0) { // cautarile de minim pentru n noduri
        // acum extrag minimul din heap
        m = minimumValue();
        cutAnElement(1);
        vizitat[m.first] = 1;

        // pentru toti vecinii ii iau si ii inserez corect in heap
        for(int k = 0; (unsigned)k < arr[m.first].size(); ++k) {
            pminA = arr[m.first][k].first;
            if( !vizitat[pminA] ) {
                pminC = arr[m.first][k].second;
                calcActual = cost[m.first] + pminC;
                if (cost[pminA] > calcActual)
                    cost[pminA] = calcActual;
                insertAnElement(make_pair(pminA, cost[pminA]));
            }
        }
    }
}

int main()
{
    freopen("dijkstra.in", "r", stdin);
    freopen("dijkstra.out", "w", stdout);
    scanf("%d %d", &N, &M);
    citireMuchii();
    dijkstra_heap(1);
    for(int i = 2; i <= N; ++i)
            printf("%d ", (cost[i] == INF) ? 0: cost[i]);
    return 0;
}