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

#define DIM 50001
#define INF 0x3f3f3f3f

int N, M;
int c[ DIM ];
bitset <DIM> f;
vector < pair <int, int> > v[ DIM ];

struct cmp {

    bool operator()( const int &a, const int &b ) {

        return c[ a ] > c[ b ];
    }
};

priority_queue < int, vector <int>, cmp > h;

int main() {

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

    int i, x, y, cst, nod, vec;
    unsigned int I;

    scanf( "%d %d", &N, &M );
    for( i = 1; i <= M; ++i ) {

        scanf( "%d %d %d", &x, &y, &cst );
        v[ x ].push_back( make_pair( y, cst ) );
    }

    memset( c, INF, sizeof( c ) );
    h.push( 1 );
    c[ 1 ] = 0;
    while( !h.empty() ) {

        nod = h.top();
        h.pop();
        f[ nod ] = 0;
        for( I = 0; I < v[ nod ].size(); ++I ) {

            vec = v[ nod ][ I ].first;
            cst = v[ nod ][ I ].second;
            if( c[ nod ] + cst < c[ vec ] ) {

                c[ vec ] = c[ nod ] + cst;
                if( !f[ vec ] ) {

                    h.push( vec );
                    f[ vec ] = 1;
                }
            }
        }
    }

    for( i = 2; i <= N; ++i )
        printf( "%d ", c[ i ] );

    return 0;
}