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

using namespace std;

int dist[nm];
VPII A[nm];

priority_queue < int, vector < int > > q;

void Dijkstra( int sursa ) {

    memset( dist, INF, nm );
    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" );

    int n, m; 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 ) {
        g << dist[i] << " ";
    }

    return 0;
}