#include <iostream>
#include <fstream>
#include <vector>

using namespace std;


const int MAX = 50002;
const int infinity = 1002;

vector <int> H, D_MIN , vecini [ MAX ] , cost [ MAX ];

void tryHeap ( unsigned int &i , unsigned int j , bool &WATCH){

    if ( j < H.size() &&  D_MIN [ H[ i ] ]  > D_MIN [ H [ j ] ]  ){

        swap ( H [ i ], H [ j ] );
        WATCH = 0;
        i = j;
    }

}

void heapUp ( unsigned int i){

    if ( D_MIN [ H[ i ] ]  < D_MIN [  H [ i/2 ] ]  && i != 1  ){
        swap ( H [ i ], H [ i/2 ] );
        i = i/2;
    }

}

void heapDown() {

    bool isHEAPED = 0;
    unsigned int i = 1;
    H [ 1 ] = H [ H.size() - 1];
    H.pop_back();

    while ( !isHEAPED ){

        isHEAPED = 1;
        // go on the min road
        if(2*i >= D_MIN.size() ) break;

        if (  D_MIN [ H [ 2*i ] ] < D_MIN [ H [ 2*i + 1 ] ] ){

            tryHeap ( i, 2*i , isHEAPED );

            if( isHEAPED )
            tryHeap ( i , 2*i + 1, isHEAPED );
        }
        else{
            tryHeap ( i, 2*i + 1 , isHEAPED );

            if(isHEAPED)
            tryHeap ( i , 2*i , isHEAPED );
        }

    }

}

void dijkstra () {

    int C_node , i; ;

    while ( H.size() ){

        C_node = H [ 1 ] ; //the node with the min cost;
        for ( i = 0 ; i < vecini [ C_node ].size() ; i++)
            if ( D_MIN [ vecini [ C_node ] [ i ] ] > D_MIN [ C_node ] + cost [ C_node] [ i ] ){

                 D_MIN [ vecini [ C_node ] [ i ] ] =  D_MIN [ C_node ] + cost [ C_node] [ i ] ;
                 heapUp ( vecini [ C_node ] [ i ] ) ;

            }

        heapDown();
    }

}



int main()
{
    ifstream f( "dijkstra.in" , ios::in) ;
    ofstream g( "dijkstra.out" , ios::out);

    int N , M , x, y , c , i;
    f>>N>>M;

    while ( M-- ){

        f>>x>>y>>c;
        vecini [ x ].push_back ( y );
        cost [ x ].push_back ( c );
    }

    D_MIN.resize( N + 1);
    H.resize ( N + 1);
    D_MIN [ 1 ] = 0;

    for ( i = 2; i <= N ; i++)
        D_MIN [ i ] = infinity ;
    for ( i = 1 ;i <= N ; i++)
        H [ i ] = i;

    dijkstra();

    for ( i = 2 ; i <= N ; i++)
        g<<D_MIN [ i ]<<" ";






    return 0;
}