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

    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 ) );
            }
        }
    }
}
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, 2 * 1e6 );
    dijkstra ( 1 );

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

    return 0;
}