#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#include <utility>
using namespace std;

#define Nmax 50002
#define inf 0x3f3f3f3f

FILE *f = fopen ( "dijkstra.in", "r" );
FILE *g = fopen ( "dijkstra.out", "w" );

vector < pair < int, int > > G[Nmax];
priority_queue < pair < int, int > > Heap;
int dist[Nmax];

int main(){

    int N, M, x, y, c;
    vector < pair < int, int > > :: iterator it;

    fscanf ( f, "%d%d", &N, &M );

    for ( int i = 2; i <= N; ++ i )
        dist[i] = inf;

    for ( int i = 1; i <= M; ++i ){
        fscanf ( f, "%d%d%d", &x, &y, &c );
        G[x].push_back ( make_pair ( y, c ) );
    }

    Heap.push ( make_pair ( 0, 1 ) );

    while ( !Heap.empty() ){
        int nod = Heap.top().second;
        Heap.pop();

        for ( it = G[nod].begin(); it < G[nod].end(); ++it ){
            if ( dist[it->first] > dist[nod] + it -> second ){
                dist[it->first] = dist[nod] + it -> second;
                Heap.push ( make_pair ( dist[it->first], it -> first  ) );
            }
        }
    }

    for ( int i = 2; i <= N; ++i )
        fprintf ( g, "%d ", dist[i] == inf ? 0 : dist[i] );

    return 0;
}