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

#define INF 0x3f3f3f3f
#define MAX_N 50005
#define MAX_S 10005

char s[ MAX_S ];
int N, M;
int cnt_s, cnt_h, dst[ MAX_N ], poz[ MAX_N ], heap[ MAX_N ];
vector < pair <int, int> > v[ MAX_N ];

void heap_up( int nod ) {

    int aux;

    while( nod > 1 ) {

        aux = nod>>1;

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

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

            nod = aux;
        }
        else
            return;
    }
}

void heap_down( int nod ) {

    int aux;

    while( nod <= cnt_h ) {

        if( nod<<1 <= cnt_h ) {

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

        if( dst[ heap[ nod ] ] > dst[ heap[ aux ] ] ) {

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

            nod = aux;
        }
        else
            return;
    }
}

void heap_push( const int &ind ) {

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

void heap_pop() {

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

void read( int &val ) {

    while( !isdigit( s[ cnt_s ] ) )
        if( ++cnt_s == MAX_S ) {

            fread( s, 1, MAX_S, stdin );
            cnt_s = 0;
        }

    val = 0;
    while( isdigit( s[ cnt_s ] ) ) {

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

            fread( s, 1, MAX_S, stdin );
            cnt_s = 0;
        }
    }
}

int main() {

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

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

    cnt_s = MAX_S - 1;

    read( N );
    read( M );

    while( M-- ) {

        read( x );
        read( y );
        read( c );

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

    cnt_h = 0;
    memset( dst, INF, sizeof( dst ) );
    memset( poz, 0, sizeof( poz ) );

    heap_push( 1 );
    dst[ 1 ] = 0;

    while( cnt_h ) {

        nod = heap[ 1 ];
        heap_pop();

        for( it = v[ nod ].begin(); it != v[ nod ].end(); ++it )
            if( dst[ nod ] + it->second < dst[ it->first ] ) {

                dst[ it->first ] = dst[ nod ] + it->second;

                if( poz[ it->first ] )
                    heap_up( poz[ it->first ] );
                else
                    heap_push( it->first );
            }
    }

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

    return 0;
}