#include <bits/stdc++.h>
#define MAXN 50000
using namespace std;
int dist[MAXN + 1];
struct cel {
    int nod , val;
};
vector< cel >edges[MAXN + 1];
queue< int >q;
int main() {
    ifstream cin( "dijkstra.in" );
    ofstream cout( "dijkstra.out" );
    int n , m , i , a , b , c , k;
    cin >> n >> m;
    for( i = 1 ; i <= m ; i++ ) {
        cin >> a >> b >> c;
        edges[a].push_back( { b , c } );
        //edges[b].push_back( { a , c } );
    }
    for( i = 2 ; i <= n ; i++ )
        dist[i] = INT_MAX;
    q.push( 1 );
    dist[1] = 0;
    while( !q.empty() ) {
        k = q.front();
        q.pop();
        for( auto x : edges[k] ) {
            //cout << dist[k] << ' ' << k << ' ' << x.nod << ' ' << x.val << '\n';
            if( dist[x.nod] > dist[k] + x.val ) {
                //cout << x.nod << ' ' << x.val << '\n';
                dist[x.nod] = dist[k] + x.val;
                q.push( x.nod );
            }
        }
    }
    for( i = 2 ; i <= n ; i++ ) {
        if( dist[i] == INT_MAX )
            dist[i] = 0;
        cout << dist[i] << ' ';
    }
    cout << '\n';
    return 0;
}