#include <fstream>
#include <vector>

const int nmax = 50000, mmax = 250000;

struct str{
    int x, y;
};

str mp( int x, int y ) {
    str sol;
    sol.x = x;
    sol.y = y;
    return sol;
}

std::vector < std::vector < str > > g;

int d[nmax];

str h[mmax];
int hsize;

void swap( str &x, str &y ) {
    str aux = x;
    x = y;
    y = aux;
}

void push( str h[], str x ) {
    h[hsize] = x;
    ++ hsize;
    int p = hsize;
    while ( p > 1 && h[p-1].y < h[p/2-1].y ) {
        swap(h[p-1], h[p/2-1]);
        p /= 2;
    }
}

void pop( str h[] ) {
    swap(h[0], h[hsize-1]);
    -- hsize;
    int  p = 1;
    while ( ( p*2 <= hsize && h[p-1].y > h[p*2-1].y ) ||
        ( p*2+1 <= hsize && h[p-1].y > h[p*2].y ) ) {

        if ( p*2+1 <= hsize && h[p*2].y < h[p*2-1].y ) {
            swap(h[p-1], h[p*2]);
            p = p*2+1;
        } else {
            swap(h[p-1], h[p*2-1]);
            p = p*2;
        }
    }
}

int main( ) {
    std::ifstream fin("dijkstra.in");
    int n, m;
    fin >> n >> m;
    g.resize(n);
    for ( int i = 0; i < m; ++ i ) {
        int x, y, z;
        fin >> x >> y >> z;
        g[x-1].push_back(mp(y-1, z));
    }
    fin.close();

    d[0] = 0;
    for ( int i = 1; i < n; ++ i ) {
        d[i] = -1;
    }
    push(h, mp(0, 0));
    while ( hsize > 0 ) {
        int x = h[0].x;
        int y = h[0].y;
        pop(h);
        if ( d[x] == y ) {
            for ( int i = 0; i < int(g[x].size()); ++ i ) {
                int xn = g[x][i].x;
                int yn = g[x][i].y;
                if ( d[xn] == -1 || d[xn] > d[x]+yn ) {
                    d[xn] = d[x]+yn;
                    push(h, mp(xn, d[xn]));
                }
            }
        }
    }

    std::ofstream fout("dijkstra.out");
    for ( int i = 1; i < n; ++ i ) {
        if ( d[i] != -1 ) {
            fout << d[i] << " ";
        } else {
            fout << "0 ";
        }
    }
    fout << "\n";
    fout.close();
    return 0;
}