#include <iostream>
#include <fstream>
#include <set>

#include <vector>

using namespace std;

const int MAX = 50003;
const int INF  = 1004;
int N , M;

set < pair<int, int> > Tree;
vector <int> vcn [ MAX ] , cst [ MAX ];
int SL [ MAX ];

void dijkstra() {

    int i, j, nd, pret;
    Tree.insert ( make_pair ( 0, 1 ) );

    while ( Tree.size() ) {
        nd =  ( * Tree.begin() ).second;
        pret = ( *Tree.begin() ).first;
         Tree.erase(*Tree.begin() );

        for ( i = 0 ; i < vcn [ nd ].size() ; i++ )
            if ( SL [ vcn [ nd ] [ i ] ] > pret + cst [ nd ] [ i ] ) {

               SL [ vcn [ nd ] [ i ] ] = pret + cst [ nd ] [ i ] ;
               Tree.insert ( make_pair ( SL [ vcn [ nd] [ i ] ] , vcn [nd][i] ) ) ;
            }


    }


}


int main() {
    int x, y, z;
    ifstream f ( "dijkstra.in" , ios::in );
    ofstream g ( "dijkstra.out" , ios::out );
    f >> N >> M;

    for ( int i = 2 ; i <= N ; i++ )
        SL [i] = INF;

    while ( M-- ) {
        f >> x >> y >> z;
        vcn[x].push_back ( y );
        cst[x].push_back ( z );
    }

    dijkstra();

    for (int i = 2 ; i <= N; i++)
      if( SL[i] == INF)
         g<<0<<" ";
      else
         g<<SL[i]<<" ";

    return 0;
}