#include<fstream>
#include<vector>

using namespace std;

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

const int inf = 1 << 30;
const int nmax = 50000;
int hn, h[ 2 * nmax + 1 ], p[ nmax + 1 ];
int d[ nmax + 1 ];
struct muchie{ int x, cost; };
vector< muchie > g[ nmax + 1 ];

inline muchie mp( int x, int cost ) {
    muchie s; s.x = x; s.cost = cost; return s;
}
inline bool in_fata( int a, int b ) {
    return ( d[ h[ a ] ] < d[ h[ b ] ] );
}
inline void heap_swap( int a, int b ) {
    p[ h[ a ] ] = b; p[ h[ b ] ] = a;
    int aux = h[ a ]; h[ a ] = h[ b ]; h[ b ] = aux;
}
void urcare( int pos ) {
    while ( pos > 1 && in_fata( pos, (pos >> 1) ) ) {
        heap_swap( pos, (pos >> 1) );
        pos >>= 1;
    }
}
void coborare( int pos ) {
    int q; bool ok = 1;
    while ( (pos << 1) <= hn && ok == 1 ) {
        q = (pos << 1);
        if ( q + 1 <= hn && in_fata( q + 1, q ) ) {
            ++ q;
        }
        if ( in_fata( q, pos ) ) {
            heap_swap( q, pos );
            pos = q;
        } else {
            ok = 0;
        }
    }
}
void heap_insert( int x ) {
    h[ ++ hn ] = x;
    p[ x ] = hn;
    urcare( hn );
}
void heap_pop() {
    heap_swap( 1, hn );
    -- hn;
    coborare( 1 );
}
void update( int nod ) {
    for( int i = 0; i < ( int )g[ nod ].size(); ++ i ) {
        if ( d[ g[ nod ][ i ].x ] > d[ nod ] + g[ nod ][ i ].cost ) {
            d[ g[ nod ][ i ].x ] = d[ nod ] + g[ nod ][ i ].cost;
            urcare( p[ g[ nod ][ i ].x ] );
            coborare( p[ g[ nod ][ i ].x ] );
        }
    }
}
int main() {
    int n, m, x, y, z;
    fin >> n >> m;
    for( int i = 0; i < m; ++ i ) {
        fin >> x >> y >> z;
        g[ x ].push_back( mp( y, z ) );
    }
    hn = 0;
    for( int i = 2; i <= n; ++ i ) {
        d[ i ] = inf;
        heap_insert( i );
    }
    d[ 1 ] = 0; heap_insert( 1 );

    while ( hn > 0 ) {
        x = h[ 1 ];
        heap_pop();
        update( x );
    }
    for( int i = 2; i <= n; ++ i ) {
        fout << d[ i ] << " ";
    }
    fout << "\n";
    fin.close();
    fout.close();
    return 0;
}