# include <fstream>
# include <algorithm>
# include <queue>
# include <vector>
# include <climits>
# define nm 50005
# define INF numeric_limits<int>::max()

using namespace std;

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

int n, m;
vector < int > dist;
vector < vector < pair < int, int > > > A;

struct cmp {
    int operator()( int x, int y ) {
        return dist[x] > dist[y];
    }
};
priority_queue < int, vector < int >, greater< int > > q;

void Dijkstra( int sursa ) {

    dist = vector < int > ( n + 1, INF );
    dist[sursa] = 0;
    q.push( sursa );

    while ( !q.empty() ) {

        int x = q.top(); q.pop();
        for ( auto it: A[x] ) {
            if ( dist[it.first] > dist[x] + it.second ) {
                dist[it.first] = dist[x] + it.second;
                q.push( it.first );
            }
        }
    }
}

int main()
{

    f >> n >> m;
    A = vector < vector < pair < int, int > > > ( n + 1 );
    for ( int i = 0; i < m; ++ i ) {
        int x, y, cost; f >> x >> y >> cost;
        A[x].push_back( make_pair( y, cost ) );
    }

    Dijkstra( 1 );

    for ( int i = 2; i <= n; ++ i ) {
        if ( dist[i] == INF )
            dist[i] = -1;
        g << dist[i] << " ";
    }

    return 0;
}