#include <bits/stdc++.h>
using namespace std;
#define st first
#define nd second
#define pb push_back
#define mp make_pair
#define oo 2000005
ifstream fin ( "dijkstra.in" );
ofstream fout ( "dijkstra.out" );
int n, m;
int dist[50002];
vector< pair<int, int> >g[50002];
priority_queue< pair<int, int> >pq;
int main() {
    fin >> n >> m;

    for ( int i = 1; i <= m; i++ ) {
        int x, y, z;
        fin >> x >> y >> z;
        g[x].pb ( mp ( y, z ) );
        //g[y].pb ( mp ( x, z ) );
    }

    fill_n ( dist + 2, n + 1, oo );
    pair<int, int> cur;
    pq.push ( mp ( 0, 1 ) );

    while ( !pq.empty() ) {
        cur = pq.top();
        pq.pop();

        if ( -cur.st > dist[cur.nd] )
            continue;

        for ( auto it : g[cur.nd] ) {
            if ( dist[cur.st] + it.nd < dist[it.st] ) {
                dist[it.st] = dist[cur.nd] + it.nd;
                pq.push ( mp ( -dist[it.st], it.st ) );
            }
        }
    }

    for ( int i = 2; i <= n; i++ )
        fout << ( dist[i] < oo ? dist[i] : 0 ) << ' ';

    return 0;
}