#include <cstdio>
#include <set>
#include <vector>
#include <map>

#define NMax 50002

using namespace std;

long n, m, x, y, z, now;
long dist[NMax];
set<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.insert ( make_pair( 0, 1 ) );
    while ( !q.empty ( ) ) {
        now = q.begin ( )->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] == 0 )
                dist[i->first] = dist[now] + i->second,
                q.insert ( make_pair ( dist[i->first], i->first ) );
        q.erase ( q.begin ( ) );
    }

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

    return 0;
}