#include <fstream>
#include <vector>

#define DIM 50010
#define INF DIM*1000

using namespace std;

vector < pair<int, int> >L[DIM];
int D[DIM], V[DIM], P[DIM], H[DIM];

int n, m, dH, x, y, k, aux, i, c, inHeap;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

void stergeRad() {
    H[1] = H[dH--];
    P[H[1]] = 1;

    int p = 1, c = 2;
    while (c <= dH) {
        if (c + 1 <= dH && D[ H[c+1] ] < D[ H[c] ])
            c++;

        if (D[ H[p] ] > D[ H[c] ]) {
            aux = H[p];
            H[p] = H[c];
            H[c] = aux;
            P[ H[p] ] = p;
            P[ H[c] ] = c;
            p = c;
            c = 2*p;
        } else
            break;
    }
}

void urca(int poz) {
    int c = poz, p = c/2;
    while (p != 0 && D[ H[c] ] < D[ H[p] ]) {
        aux = H[c];
        H[c] = H[p];
        H[p] = aux;
        P[H[p]] = p;
        P[H[c]] = c;
        c = p;
        p = c/2;
    }
}

int main() {
    fin>>n>>m;
    for (i=1;i<=m;i++) {
        fin>>x>>y>>c;
        L[x].push_back(make_pair(y,c));
    }

    for (i=1;i<=n;i++)
        D[i] = INF;
    D[1] = 0;

    H[1] = 1;
    P[1] = 1;
    dH = 1;
    while (dH) {
        k = H[1];
        stergeRad();

        V[k] = 1;

        for (i=0;i<L[k].size(); i++) {
            x = L[k][i].first;
            if (D[x] > D[k] + L[k][i].second) {
                inHeap = (D[x] != INF);
                D[x] = D[k] + L[k][i].second;
                if (inHeap)
                    urca( P[x] );
                else {
                    dH ++;
                    H[dH] = x;
                    P[x] = dH;
                    urca(dH);
                }
            }
        }

    }

    for (i=2;i<=n;i++)
        if (D[i] == INF)
            fout<<"0 ";
        else
            fout<<D[i]<<" ";

    return 0;
}