# include <iostream>
# include <fstream>
# include <algorithm>
# include <queue>
# include <vector>
# include <cstring>
# include <cstdio>
# include <climits>
# define nm 50005
# define VPII vector < pair < int, int > >

using namespace std;

int n, m;
vector < int > dist;
VPII A[nm];
int INF = numeric_limits < int > :: max();

priority_queue < int, vector < int >, greater < int > > q;

void Dijkstra( int sursa ) {

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

    VPII :: iterator it;
    while ( !q.empty() ) {

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

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

    f >> n >> m;
    while ( m -- ) {
        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 )
            g << 0 << " ";
        else
            g << dist[i] << " ";
    }

    return 0;
}