#include <stdio.h>
#define M_MAX 250000
#define N_MAX 50000
#define INF 2000000000

typedef struct{
    int vf, next, w;
}graf;

graf adj[ M_MAX + 1 ];
int ult[ N_MAX + 1 ];
int heap[ N_MAX + 1 ], nod[ N_MAX + 1 ], ph[ N_MAX + 1 ], dr = 2;
int val[ N_MAX + 1 ];

inline void intersch ( int x, int y ){
    int aux;
    ph[ nod [ x ] ] = y;  ph[ nod[ y ] ] = x;
    aux = heap[ x ];  heap[ x ] = heap[ y ];  heap[ y ] = aux;
    aux = nod[ x ];  nod[ x ] = nod[ y ];  nod[ y ] = aux;
    return ;
}

inline void urc ( int x ){
    while ( x > 1 && heap[ x / 2 ] > heap[ x ] ){
        intersch ( x, x / 2 );
        x /= 2;
    }
    return ;
}
inline void cobor ( int x ){
    int a, b, poz, gasit = 1;
    while ( x * 2 < dr && gasit ){
        poz = x;
        gasit = 0;
        a = x * 2;
        b = a + 1;
        if ( heap[ a ] < heap[ x ] ){
            poz = a;
            gasit = 1;
        }
        if ( b < dr ){
            if ( heap[ b ] < heap[ poz ] ){
                poz = b;
                gasit = 1;
            }
        }
        intersch ( x, poz );
        x = poz;
    }
    return ;
}

void dijkstra ( int n ){
    nod[ 1 ] = 1;
    heap[ 1 ] = 0;
    ph[ 1 ] = 1;
    int poz;
    while ( dr > 1 ){
        poz = ult[ nod[ 1 ] ];
        while ( poz > 0 ){
            if ( val[ adj[ poz ] . vf ] == INF ){
                if( ph[ adj[ poz ] . vf ] != 0 ){
                    if ( heap[ ph[ adj[ poz ] . vf ] ] > heap[ 1 ] + adj[ poz ] . w ){
                        heap[ ph[ adj[ poz ] . vf ] ] = heap[ 1 ] + adj[ poz ] . w;
                        urc ( ph[ adj[ poz] . vf ] );
                    }
                }
                else{
                    heap[ dr ] = heap[ 1 ] + adj[ poz ] . w;
                    nod[ dr ] = adj[ poz ] . vf;
                    ph[ adj[ poz ] . vf ] = dr;
                    urc( dr );
                    dr++;
                }
            }
            poz = adj[ poz ] . next;
        }
        val[ nod[ 1 ] ] = heap[ 1 ];
        intersch ( dr - 1, 1 );
        dr--;
        cobor ( 1 );
    }
    return ;
}

int main()
{
    FILE *in = fopen ( "dijkstra.in", "r" );
    int n, m;
    fscanf ( in, "%d%d", &n, &m );
    int i, x, y, g;
    for ( i = 1; i <= m; i++ ){
        fscanf ( in, "%d%d%d", &x, &y, &g );
        adj[ i ] . vf = y;
        adj[ i ] . next = ult[ x ];
        adj[ i ] . w = g;
        ult[ x ] = i;
    }
    fclose ( in );
    for ( i = 2; i <= n; i++ )  val[ i ] = INF;
    dijkstra( n );
    FILE *out = fopen ( "dijkstra.out", "w" );
    for ( i = 2; i <= n; i++ ){
        if ( val[ i ] != INF )  fprintf ( out, "%d ", val[ i ] );
        else                    fprintf ( out, "0 " );
    }
    fclose ( out );
    return 0;
}