#include <stdio.h>
#include <limits.h>

#define INF INT_MAX

#define N_MAX 50000
#define M_MAX 250000

typedef struct {
    int node, cost;
} Pair;

Pair mp( int node, int cost ) {
    Pair p;
    p.node = node;
    p.cost = cost;
    return p;
}

Pair list[ M_MAX + 1 ];
int next[ M_MAX + 1 ];
int beg[ N_MAX + 1 ], end[ N_MAX + 1 ]; // Inceputul si sfarsitul de lista
int sp;

void add( int v1, int v2, int cost ) {
    list[ ++ sp ] = mp( v2, cost );
    if( beg[ v1 ] == 0 ) {
        beg[ v1 ] = end[ v1 ] = sp;
    } else {
        next[ end[ v1 ] ] = sp;
        end[ v1 ] = sp;
    }
}

Pair heap[ N_MAX + 1 ];
int len;

inline int dad( int x ) {
    return x / 2;
}
inline int lson( int x ) {
    return x * 2;
}
inline int rson( int x ) {
    return x * 2 + 1;
}

void push( Pair p ) {
    heap[ ++ len ] = p;
    int curr = len;
    while( curr != 1 ) {
        if( heap[ curr ].cost < heap[ dad( curr ) ].cost ) {
            Pair aux = heap[ curr ];
            heap[ curr ] = heap[ dad( curr ) ];
            heap[ dad( curr ) ] = aux;
            curr = dad( curr );
        } else {
            curr = 1;
        }
    }
}

void pop( ) {
    heap[ 1 ] = heap[ len -- ];
    int curr = 1, finish = 0;
    while( !finish ) {
        int max = curr;
        if( lson( curr ) <= len && heap[ max ].cost > heap[ lson( curr ) ].cost ) {
            max = lson( curr );
        }
        if( rson( curr ) <= len && heap[ max ].cost > heap[ rson( curr ) ].cost ) {
            max = rson( curr );
        }
        if( max != curr ) {
            Pair aux = heap[ max ];
            heap[ max ] = heap[ curr ];
            heap[ curr ] = aux;
            curr = max;
        } else {
            finish = 1;
        }
    }
}

int mind[ N_MAX + 1 ];

void Dijkstra( ) {
    push( mp( 1, 0 ) );
    while( len ) {
        Pair best = heap[ 1 ];
        pop( );
        int curr = beg[ best.node ];
        while( curr ) {
            if( mind[ list[ curr ].node ] > best.cost + list[ curr ].cost ) {
                mind[ list[ curr ].node ] = best.cost + list[ curr ].cost;
                push( mp( list[ curr ].node, mind[ list[ curr ].node ] ) );
            }
            curr= next[ curr ];
        }
    } 
}

int main( ) {
    FILE * fin, * fout;
    fin = fopen( "dijkstra.in", "r" );
    fout = fopen( "dijkstra.out", "w" );

    int N, M;
    fscanf( fin, "%d%d", &N, &M );

    int i;
    for( i = 1; i <= M; i ++ ) {
        int v1, v2, cost;
        fscanf( fin, "%d%d%d", &v1, &v2, &cost );
        add( v1, v2, cost );
    }

    mind[ 1 ] = 0;
    for( i = 2; i <= N; i ++ ) {
        mind[ i ] = INF; 
    }

    Dijkstra( );

    for( i = 2; i <= N; i ++ ) {
        fprintf( fout, "%d ", mind[ i ] == INF ? 0 : mind[ i ] );
    }

    fclose( fin );
    fclose( fout );
}