#include <fstream>
#include <vector>

using namespace std;

int n, m, i, j, k, dim, dist[50005], drum[50005], heap[50005], poz[50005];
vector<pair<int, int>> d[50005];

void pushup(int p) {
    int dst;

    dst = dist[heap[p]];        /// distanta pana la nodul de pe pozitia p
    while(p > 1 && dst > dist[heap[p / 2]]) {
        poz[heap[p]] = p / 2;   /// pentru ca interschimbam valorile, trebuie sa interschimbam pozitiile in heap
        poz[heap[p / 2]] = p;
        swap(heap[p], heap[p / 2]);
        p /= 2;
    }
}

void pushdown(int p) {
    int fiu;

    fiu = 1;
    while(fiu) {
        fiu = 0;
        if(p * 2 <= dim) {                      /// daca avem cel putin un fiu
            fiu = p * 2;
            if(p * 2 + 1 <= dim && dist[heap[p * 2 + 1]] < dist[heap[p * 2]])
                fiu = p * 2 + 1;                /// alegem fiul pentru care avem cost minim
            if(dist[heap[fiu]] > dist[heap[p]]) /// daca fiul cu distanta minima are distanta mai mare decat distanta pana la tatal lui, ne oprim
                fiu = 0;
        }
        if(fiu) {
            swap(heap[fiu], heap[p]);           /// interschimb valorile din fii
            swap(poz[heap[p]], poz[heap[fiu]]); /// interschimb pozitiile din heap ale valorilor
            p = fiu;
        }
    }
}

int main()
{
    ifstream f("dijkstra.in");
    ofstream g("dijkstra.out");
    int infinit = 2000000000;

    f >> n >> m;
    while(m) {
        f >> i >> j >> k;
        d[i].emplace_back(j, k);    /// avem arc de la i la j, cu costul k
        m--;
    }
    f.close();

    for(i = 2; i <= n; i++) {
        drum[i] = dist[i] = infinit;    /// drumul & distanta minima pana la nodul i
        heap[i - 1] = i;                /// construiesc heap-ul
        poz[i] = i - 1;                 /// pozitia elementului i in heap
    }
    drum[i] = dist[1] = 0;

    i = 1;
    dim = n - 1;    /// dimensiunea heap-ului
    for(k = 1; k <= n; k++) {
        for(j = 0; j < d[i].size(); j++)
            if(drum[i] + d[i][j].second < drum[d[i][j].first]) {
                dist[d[i][j].first] = drum[d[i][j].first] = drum[i] + d[i][j].second;
                pushup(poz[d[i][j].first]);
            }

        dist[i] = infinit;    /// cand nodul este folosit, i se atribuie o distanta mare, pentru a reface heap-ul
        pushdown(1);       /// refac heap-ul
        dim--;                /// elimin un nod
        i = heap[1];          /// aleg mereu nodul din heap pana la care am distanta minima
    }

    for(i = 2; i <= n; i++)
        if(drum[i] >= infinit)
            g << "0 ";
        else
            g << drum[i] << " ";
    g << '\n';
    g.close();

    return 0;
}