#include <bits/stdc++.h>
using namespace std;

ifstream in ( "dijkstra.in"  );
ofstream out( "dijkstra.out" );

struct E{
    int v, c;

    bool operator <( E o ) const {
        return this -> c > o.c;
    }

    E( int v, int c ) {
        this -> v = v;
        this -> c = c;
    }
}; priority_queue<E> pq;
vector<int> dp; vector< vector<E> > g;

int main( void ) {

    int n, m; in >> n >> m;

    g.resize( n + 1 );
    dp.resize( n + 1, INT_MAX );

    for( int i = 1; i <= m; i ++ ) {
        int x, y, z; in >> x >> y >> z;
        g[x].push_back( E(y, z) );
    }

    pq.push( E(1, 0) );
    while( !pq.empty() ) {
        E e = pq.top(); pq.pop();

        if( dp[e.v] == INT_MAX ) {
            dp[e.v] = e.c;

            vector<E> :: iterator it;
            for( it = g[e.v].begin(); it != g[e.v].end(); it ++ ) {
                if( dp[it->v] == INT_MAX )
                    pq.push( E( it->v, dp[e.v] + it->c ) );
            }
        }
    }

    for( int i = 2; i <= n; i ++ )
        out << ( (dp[i] == INT_MAX) ? 0 : dp[i] ) << " ";
    out << endl;

    return 0;
}