#include <cstdio>
#include <queue>
#include <algorithm>
#include <vector>
#include <map>

#define NMax 50002

using namespace std;

long n, m, x, y, z, now;
long dist[NMax];
//priority_queue<pair<long, long>, vector<pair<long, long> >, greater<pair<long, long> > > q;
queue<long> q;
vector<pair<long, long> > vertex[NMax];

int main ( )
{
    freopen ( "dijkstra.in", "r", stdin );
    freopen ( "dijkstra.out", "w", stdout );

    scanf ( "%ld %ld", &n, &m );
    for ( long i = 1; i <= m; i++ )
        scanf ( "%ld %ld %ld", &x, &y, &z ),
        vertex[x].push_back ( make_pair ( y, z ) );

    dist[1] = 0;
    //q.push ( make_pair( 0, 1 ) );
    q.push ( 1 );
    while ( !q.empty ( ) ) {
        //now = q.top ( ).second;
        now = q.front ( );
        for ( vector<pair<long, long> >::iterator i = vertex[now].begin ( ); i != vertex[now].end ( ); i++ )
            if ( dist[now] + i->second < dist[i->first] || dist[i->first] == 0 )
                dist[i->first] = dist[now] + i->second,
                //q.push ( make_pair ( dist[i->first], i->first ) );
                q.push ( i->first );
        q.pop ( );
    }

    for ( long i = 2; i <= n; i++ )
        printf ( "%ld ", dist[i] );

    return 0;
}