#include <iostream>
#include <fstream>
#include <utility>
#include <bitset>
#include <vector>
#include <algorithm>
#define ll int
#define F first
#define S second
using namespace std;

bool comp(const pair<ll, ll> & a, const pair<ll, ll> & b) {
    return a.S > b.S;
}
int main() {
    ll n,m;
    ifstream fin("dijkstra.in");
    ofstream fout("dijkstra.out");
    fin>>n>>m;
    vector< vector<pair<ll, ll> > > v(n);
    for(ll i=0; i<m; ++i) {
        ll a;
        pair<ll, ll> b;
        fin>>a>>b.F>>b.S;
        --b.F;
        v[a-1].push_back(b);
    }

    bitset<50001> ka;
    vector<ll> et(n);
    for(int i=0; i<n; ++i) et[i]=(ll)1<<30;
    vector< pair<ll, ll> > j;
    make_heap(j.begin(), j.end(), comp);
    j.push_back(make_pair(0, 0));
    push_heap(j.begin(), j.end(), comp);

    for(;j.size()>0;) {
        pair<ll, ll> q=j.front();
        pop_heap(j.begin(), j.end(), comp);
        j.pop_back();
        if(ka[q.F]) continue;
        ka[q.F]=1;
        et[q.F]=q.S;
        for(ll i=0; i<v[q.F].size(); ++i) {
            ll uk=v[q.F][i].F;
            ll ue=v[q.F][i].S+q.S;
            if(ka[uk] || ue >= et[uk]) continue;
            j.push_back(make_pair(uk, ue));
            push_heap(j.begin(), j.end(), comp);
        }

    }
    for(ll i=1; i<n; ++i) {
        if(ka[i]==0) fout<<0<<' ';
        else fout<<et[i]<<' ';
    }
}