#include <fstream>

using namespace std;

const int Inf = 1<<30;
const int Nmax = 500;

int main() {
    int i, j, x, y, r, min, N, M, poz;
    int S[Nmax], D[Nmax], T[Nmax], A[Nmax][Nmax];

    ifstream f("dijkstra.in");
    f>>N>>M;

    for(i = 1; i <= N; ++i) {
        S[i] = D[i] = T[i] = A[i][i] = 0;
        for(j = 1; j <= N; ++j)
            if(i != j) A[i][j] = Inf;
    }

    for(i = 1; i <= M; ++i) {
        f>>x>>y;
        f>>A[x][y];
    }

    r = 1;
    f.close();

    for(i = 1; i <= N; ++i) {
        D[i] = A[r][i];
        if(i != r)
            if(D[i] < Inf) T[i] = 1;
    }

    for(i = 1; i < N; ++i) {
        min = Inf;
        for(j = 1; j <= N; ++j)
            if(!S[j])
                if(D[j] < min) {
                    min = D[j];
                    poz = j;
                }

        S[poz] = 1;
        for(j = 1; j <= N; ++j)
            if(!S[j])
                if(D[j] > D[poz]+A[poz][j]) {
                    D[j] = D[poz]+A[poz][j];
                    T[j] = poz;
                }
    }

    ofstream g("dijkstra.out");
    for(i = 2; i <= N; ++i) g<<D[i]<<" ";
    g.close();

    return 0;
}