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

#define NMax 50002

using namespace std;

long n, m, x, y, z, now;
vector<long> dist ( NMax, 99999 );
priority_queue<pair<long, long>, vector<pair<long, long> >, greater<pair<long, 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 ) );
    while ( !q.empty ( ) ) {
        now = q.top ( ).second;
        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] = dist[now] + i->second,
                q.push ( make_pair ( dist[i->first], i->first ) );
        q.pop ( );
    }

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

    return 0;
}