#include <bits/stdc++.h>

using namespace std;

const int MAXN = 5e4 , MAXD = 1e9;
vector < pair < int , int > > vec[MAXN + 1];
priority_queue < pair < int , int > > pqn;
int dnod[MAXN + 1];
int main () {
    ifstream fin ( "dijkstra.in" );
    ofstream fout ( "dijkstra.out" );
    ios_base :: sync_with_stdio ( 0 );
    cin.tie ( 0 );
    cout.tie ( 0 );
    int n , m , i , a , b , c , pqt , pqc , vnod , cnod;

    fin >> n >> m;
    for ( i = 1 ; i <= m ; i++ ) {
        fin >> a >> b >> c;
        vec[a].push_back ( { b , c } );
    }
    pqn.push ( { 0 , 1 } );
    for ( i = 1 ; i <= n ; i++ )
        dnod[i] = MAXD + 1;
    dnod[1] = 0;
    while ( pqn.empty () == 0 ) {
        pqc = -( pqn.top ().first );
        pqt = pqn.top ().second;
        pqn.pop ();
        if ( dnod[pqt] == pqc )
            for ( i = 0 ; i < vec[pqt].size () ; i++ ) {
                vnod = vec[pqt][i].first;
                cnod = vec[pqt][i].second;
                if ( cnod + dnod[pqt] < dnod[vnod] ) {
                    dnod[vnod] = dnod[pqt] + cnod;
                    pqn.push ( { -dnod[vnod] , vnod } );
                }
            }
    }
    for ( i = 2 ; i <= n ; i++ ) {
        if ( dnod[i] == MAXD + 1 )
            fout.put ( '0' );
        else
            fout << dnod[i];
        fout.put ( ' ' );
    }
    fout.put ( '\n' );
    return 0;
}