#include <fstream>
#include <algorithm>
#define inf 1215752192

using namespace std;

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

struct point{
    int x, c;
    point *y;
} *g[50001], *q;

int h[50001], p[50001], d[50001], n, m; //h - vector e heap, p - vector de pozitii, d - vector de distante

inline void intro(int x, int y, int c) {
    point *q = new point;
    q->x = y;
    q->c = c;
    q->y = g[x];
    g[x] = q;
}

inline void swapp(int i, int j) {
    swap(h[i], h[j]);
    swap(p[h[i]], p[h[j]]);
}

void heapup(int i) { //percolate
    if ( d[h[i/2]] < d[h[i]] ) return;  //daca distanta pana la tata < distanta la nod, oprim
    swapp(i, i/2);  //altfel interschimbam nodurile
    heapup(i/2);
}

void heapdown(int i) { //sift
    int st, dr; //st - fiul din stanga, dr - fiul din dreapta
    if ( i * 2 >= m ) return; //daca fiul depaseste lungimea heapului oprim
    st = d[h[i*2]];
    if ( i * 2 + 1 <= m ) dr = d[h[i*2+1]];
    else dr = st + 1;
    if ( st < dr ) {
        if ( d[h[i]] <= st ) return; //daca distanta actuala e mai mica decat distanta la fiu, atunci oprim, totul e in parametrii
        swapp(i*2, i);
        heapdown(i*2);
    } else {
        if ( d[h[i]] <= dr ) return;
        swapp(i*2+1, i);
        heapdown(i*2+1);
    }
}

int main()
{
    int i, x, y, c, nod;
    fin >> n >> m;
    for ( i = 1; i <= m; ++i ) {
        fin >> x >> y >> c;
        intro(x, y, c);
    }
    for ( i = 1; i <= n; ++i ) {
        d[i] = inf;
        h[i] = p[i] = i;
    }
    m = n;
    d[1] = 0;
    for ( i = 0; i < n; ++i ) {
        nod = h[1];
        swapp(1, m);
        m--;
        heapdown(1);
        for ( q = g[nod]; q != NULL; q = q-> y ) {
            if ( d[q->x] > d[nod] + q->c ) {
                d[q->x] = d[nod] + q->c;
                heapup(p[q->x]);
            }
        }
    }
    for ( i = 2; i <= n; ++i ) {
        if ( d[i] >= inf ) fout << 0 << " ";
        else fout << d[i] << " ";
    }
    return 0;
}