#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
//#include <bits/stdc++.h>
#define in fin
#define out fout
#define mkp make_pair
#define oo 1000000000
#define fr first
#define sc second

using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

vector< pair<int, int> > v[50005];
int d[50005];

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m; in >> n >> m;

    for(int i = 0; i < m; i++){
        int a, b, c; in >> a >> b >> c;
        v[a].push_back( mkp(b, c) );
    }

    priority_queue< pair<int, int>, vector< pair<int, int> >, greater< pair<int, int> > > pq;
    d[1] = 0;
    for(int i = 2; i <= n; i++) d[i] = oo;

    for(int i = 0; i < v[1].size(); i++){
        pq.push( mkp( d[1] + v[1][i].sc, v[1][i].fr ) );
        d[ v[1][i].fr ] = d[1] + v[1][i].sc; 
    }

    while(!pq.empty()){
        pair<int, int> p = pq.top(); pq.pop();
        int nod = p.sc;
        for(int i = 0; i < v[nod].size(); i++){
            if( d[ v[nod][i].fr ] != oo ) continue;
            pq.push( mkp( d[nod] + v[nod][i].sc, v[nod][i].fr ) );
            d[ v[nod][i].fr ] = d[nod] + v[nod][i].sc;
        }
    }

    for(int i = 1; i <= n; i++){
        if(d[i] == oo) d[i] = 0;
    }
    for(int i = 2; i <= n; i++) out << d[i] << " ";
    out << '\n';

    return 0;
}