#include <iostream>
#include <list>
#include <algorithm>
#include <cstdio>
#include <utility>

using namespace std;

int n, m, rad;
list <pair<int, int> > v [ 50009 ];
int d [ 50009 ];
int rd [ 300 ];
int ird [ 300 ];
bool u [ 50009 ];

int main() {
    freopen ( "dijkstra.in", "rt", stdin );
    freopen ( "dijkstra.out", "wt", stdout );
    list <pair<int, int> > :: iterator it;
    int i, j, x, y, z, nod, loc, mloc;
    cin >> n >> m;
    for ( i = 0; i < m; ++ i ) {
        cin >> x >> y >> z;
        v [x].push_back (make_pair (y, z));
    }
    for ( rad = 1; rad * rad <= n; ++ rad );
    -- rad;
    memset ( d, 127, sizeof ( d ) );
    memset ( rd, 127, sizeof ( rd ) );
    d [ 1 ] = 0;
    rd [ 0 ] = d [0];
    ird [ 0 ] = 0;
    nod = 1;
    u [ nod ] = true;
    for ( i = 1; i < n; ++ i ) {
        for ( it = v [nod].begin (); it != v [nod].end (); ++ it ) {
            if ( ! u [ it -> first ] && d [ it -> first ] > d [ nod ] + it -> second ) {
                d [ it -> first ] = d [ nod ] + it -> second;
                loc = (it->first) / rad;
                if ( rd [loc] > d [ it -> first ] ) {
                    rd [ loc ] = d [ it -> first ];
                    ird [ loc ] = it -> first;
                }
            }
        }
        loc = n / rad;
        mloc = 0;
        for ( j = 0; j <= loc; ++ j ) {
            if ( d [mloc] > d [ird [ j ]] && ! u [ird [j]] ) {
                mloc = ird [j];
            }
        }
        loc = mloc / rad;
        loc = loc * rad;
        nod = mloc;
        u [ nod ] = true;
        mloc = nod / rad;
        rd [ mloc ] = d [ 0 ];
        for ( j = loc; j < rad; ++ j ) {
            if ( ! u [ j ] && d [ j ] < rd [ mloc ] ) {
                rd [ mloc ] = d [ j ];
                ird [ mloc ] = j;
            }
        }

    }
    for ( i = 2; i <= n; ++ i )
        if ( d [ i ] != d [ 0 ] )   cout << d [i] << ' ';
        else                        cout << "0 ";
    cout << '\n';
    return 0;
}