#include <fstream>
#include <vector>
#define DIM 50010
#define INF 250000000
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

vector< pair<int, int> > L[DIM];
int D[DIM], P[DIM], H[DIM], n, m, i, x, y, c, p, dH, k, inHeap;

void swap(int &a, int &b) {
    int aux = a;
    a = b;
    b = aux;
}

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;
    dH = 1;
    P[1] = 1;  // P[i] = pe ce pozitie e in heap nodul i

    while (dH) {
        // iau minimul din D, adica elementul din varful heapului
        k = H[1];
        H[1] = H[dH--];
        P[H[1]] = 1;
        // corectez heapul stricat de radacina
        p = 1;
        c = 2*p;
        while (c <= dH) {
            if(c+1<=dH && D[ H[c+1] ] < D[ H[c] ])
                c++;

            if (D[ H[p] ] > D[ H[c] ]) {
                swap(H[p], H[c]);
                P[ H[p] ] = p;
                P[ H[c] ] = c;
            }
            else
                break;

            p = c;
            c = 2*p;
        }


        for (i=0;i<L[k].size();i++)
            if (D[  L[k][i].first  ] > D[k] + L[k][i].second) {
                if (D[  L[k][i].first  ] == INF)
                    inHeap = 0;
                else
                    inHeap = 1;

                D[  L[k][i].first  ] = D[k] + L[k][i].second;

                if (!inHeap) {
                    dH++;
                    H[dH] = L[k][i].first;
                    P[H[dH]] = dH;
                    c = dH;
                } else
                    c = P[ L[k][i].first ];
                p = c/2;

                while (p > 0) {
                    if (D[ H[p] ] > D[ H[c] ]) {
                        swap(H[p], H[c]);
                        P[ H[p] ] = p;
                        P[ H[c] ] = c;
                    } else
                        break;
                    c = p;
                    p = p/2;
                }

            }
    }

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

    return 0;
}