#include <fstream>

using namespace std ;

const int NMAX = 50001; ;
const int INF = 0x3f3f3f3f ;

ifstream cin("dijkstra.in") ;
ofstream cout("dijkstra.out") ;

struct graf {

int nod, cost;
graf *next ;

};


int N, M ;
graf * A[NMAX] ;
int D[NMAX], H[NMAX], poz[NMAX], K;


inline void add(int unde, int ce, int cost)
{

    graf *q = new graf ;
    q -> nod = unde ;
    q -> cost = cost ;
    q -> next = A[unde] ;
    A[unde] = q ;
}


inline void Read()
{
    cin >> N >> M ;

    int X, Y, Z ;

    for(int i = 1 ; i <= M ; ++ i)
    {

        cin >> X >> Y >> Z ;
        add(X, Y, Z) ;
    }



}


void swap(int a, int b) {

    int aux = H[a] ;
    H[a] = H[b] ;
    H[b] = aux ;

}


inline void uphead(int cat) {

    int father ;

    while(cat  > 1) {
        father= cat >> 1 ;

        if( D[ H [father]] > D[ H [ cat]])
        {

            poz [ H [ cat] ] = father ;
            poz [ H [ father] ] = cat ;
            swap(father, cat) ;

            cat = father ;

        }
        else cat = 1 ;
    }



}



inline void downheap(int cat) {

int F ;

while(cat <= K) {


    F = cat ;
    if((cat << 1) <= K )
    {

        F = cat << 1 ;

        if( F + 1 <= K )
        {
           if( D[ H [ F  +1 ] ] < D[ H[F]])
             ++ F ;
        }


    }
    else return  ;


    if( D[ H[cat] ] > D[ H[F] ] )
    {

        poz[ H[cat] ] = F ;
        poz[ H[F] ] = cat ;
        swap(cat, F) ;

        cat = F ;

    }

    else return ;

}

}




inline void Dijkstra() {


    for(int i = 2 ; i <= N ; ++ i)
    {
        D[i] = INF ;
        poz[i] = -1 ;
        poz[1] = 1 ;
        H[ ++ K] = 1 ;

        while( K )
        {
            int MIN = H[1] ;
            swap(1, K) ;
            poz [ H [ 1 ] ] = 1 ;
             -- K ;

             downheap(1) ;
             graf *q = A[MIN] ;

             while(q) {


                if(D[q -> nod] > D[MIN] + q -> cost)
                    D[q -> nod] = D[MIN] + q -> cost ;

                if(poz[q -> nod] != -1)
                    uphead(poz[q -> nod]) ;
                else {
                    H[ ++ K] = q -> nod ;
                    poz[ H[K] ] = K ;
                    uphead( K ) ;
                }

             }

             q = q -> next ;

        }

    }

}





int main()
{
   Read() ;
   Dijkstra() ;

   for( int i = 2 ; i <= N ; ++ i )
       cout <<  (D[i] == INF ? 0 : D[i]) << '\n';



   cin.close() ;
   cout.close() ;
    return 0 ;
}