#include <vector>
#include <iostream>
#include <fstream>
using namespace std;

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

const int MAX = 50003 , infinity = 1003 ;

int  SOL [ MAX ] ,  POS [ MAX ] , VIZ [ MAX ];
vector < int > heap , vec [ MAX ] , COST [ MAX ] ;

void schimb ( int i , int j){

    int aux = heap [ i ];
    heap [ i ] = heap [ j ];
    heap [ j ] = aux;

    aux =POS [ i ];
    POS [ i ]  =  POS [ j ];
    POS [ j ] = aux;

}

void heapUP ( int pos ){

    while ( pos > 1 && SOL [  heap [ pos ] ] < SOL [ heap [pos / 2 ] ] ){
        schimb ( pos , pos/2);
        pos/= 2;
    }

}

void heapDown ( int pos ){

    bool FINHEAP = 0;
    int j;

    while ( !FINHEAP && 2*pos < heap.size() ){

        FINHEAP = 1 ;


        if ( SOL [ heap [pos ] ] > SOL [ heap [ pos*2 ] ] ){
            FINHEAP = 0;
            j = 2*pos;
        }

        if ( SOL [ heap [pos ] ] > SOL [ heap [pos*2 + 1 ] ] && SOL [ heap [pos*2 + 1] ] < SOL [ heap [pos*2 ] ] ){
            FINHEAP = 0;
            j = 2*pos + 1;
        }

        if (!FINHEAP){
            schimb ( pos , j);
            pos = j;
        }

    }
}

void heapify (){

    schimb( 1 , heap.size() -1 );
    heap.pop_back();
    heapDown ( 1 );

}

void dijkstra(){
    int i;
    int node;

    while ( heap.size() ){

        node = heap [ 1 ];
        VIZ [ node ] = 1;

        for ( i = 0 ; i < vec [node].size() ; i++ ){
            if ( !VIZ [ vec [ node] [ i ] ] && SOL [ vec [node] [ i ] ]  > SOL [ node ] + COST [ node ] [ i ] ){

                SOL [ vec [node] [ i ] ]  = SOL [ node ] + COST [ node ] [ i ] ;
                heapUP ( POS [vec [ node] [ i ] ]  );

            }

        }

        heapify();
    }


}

int main()
{

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

    f>>N>>M;
    SOL [ 1 ] = 0;
    POS [ 1 ] = 1;
    heap.push_back ( 0 );
    heap.push_back ( 1 );


    for ( i = 2 ; i <= N ; i++){
        SOL [ i ]  = infinity;
        POS [ i ] = i;
        heap.push_back( i );
    }


    while ( M-- ){
        f>>x>>y>>c;
        vec [x].push_back(y);
        COST [x].push_back (c);

    }


    dijkstra();
    for ( i = 2 ; i <= N ; i++)
        if( SOL [ i ] == infinity)
            g<<"0 ";
        else
            g<<SOL [ i ]<<" ";

    return 0;

}