#include <algorithm>
#include <vector>
using namespace std;

#define DIM 50001
#define INF 0x3f3f3f3f
#define MAX 10001

char s[ MAX ];
int N, M, K;
int cnt, cst[ DIM ], poz[ DIM ], heap[ DIM ];
vector < pair <int, int> > v[ DIM ];

inline void heap_up( int nod ) {

    int aux;

    while( nod > 1 ) {

        aux = nod>>1;
        if( cst[ heap[ aux ] ] > cst[ heap[ nod ] ] ) {

            swap( heap[ aux ], heap[ nod ] );
            poz[ heap[ aux ] ] = aux;
            poz[ heap[ nod ] ] = nod;
            nod = aux;
        }
        else
            return;
    }
}

inline void heap_down( int nod ) {

    int aux;

    while( nod <= cnt ) {

        aux = nod;
        if( nod<<1 <= cnt ) {

            aux = nod<<1;
            if( aux+1 <= cnt && cst[ heap[ aux+1 ] ] < cst[ heap[ aux ] ] )
                ++aux;
        }
        else
            return;

        if( cst[ heap[ aux ] ] < cst[ heap[ nod ] ] ) {

            swap( heap[ aux ], heap[ nod ] );
            poz[ heap[ aux ] ] = aux;
            poz[ heap[ nod ] ] = nod;
            nod = aux;
        }
        else
            return;
    }
}

inline void heap_push( const int &ind ) {

    heap[ ++cnt ] = ind;
    poz[ ind ] = cnt;
    heap_up( cnt );
}

inline void heap_pop() {

    heap[ 1 ] = heap[ cnt-- ];
    poz[ heap[ 1 ] ] = 1;
    heap_down( 1 );
}

inline void read( int &val ) {

    while( !isdigit( s[ K ] ) )
        if( ++K == MAX ) {

            fread( s, 1, MAX, stdin );
            K = 0;
        }
    val = 0;
    while( isdigit( s[ K ] ) ) {

        val = val*10 + s[ K ] - '0';
        if( ++K == MAX ) {

            fread( s, 1, MAX, stdin );
            K = 0;
        }
    }
}

int main() {

    freopen( "dijkstra.in", "r", stdin );
    freopen( "dijkstra.out", "w", stdout );

    int i, x, y, c, ind;
    vector < pair <int, int> > :: iterator it;

    K = MAX-1;
    read( N );
    read( M );
    for( i = 0; i < M; ++i ) {

        read( x );
        read( y );
        read( c );
        v[ x ].push_back( make_pair( y, c ) );
    }

    memset( cst, INF, sizeof( cst ) );
    ++cnt;
    heap_push( 1 );
    cst[ 1 ] = 0;
    poz[ 1 ] = 1;
    while( cnt ) {

        ind = heap[ 1 ];
        heap_pop();
        for( it = v[ ind ].begin(); it != v[ ind ].end(); ++it )
            if( cst[ ind ] + it->second < cst[ it->first ] ) {

                cst[ it->first ] = cst[ ind ] + it->second;
                if( poz[ it->first ] )
                    heap_up( poz[ it->first ] );
                else
                    heap_push( it->first );
            }
    }

    for( i = 2; i <= N; ++i )
        if( cst[ i ] == INF )
            printf( "0 " );
        else
            printf( "%d ", cst[ i ] );

    return 0;
}