#include <iostream>
#include <fstream>
#include <vector>
#include <utility>
#include <algorithm>
#include <bitset>
#define F first
#define S second
using namespace std;
bool comp(const pair<int, int> & a, const pair<int, int> & b) {
    return a.S > b.S;
}
int main() {
    int n, m;
    ifstream fin("dijkstra.in");
    ofstream fout("dijkstra.out");
    fin>>n>>m;
    vector<pair<int, int> > v[50001];
    for(int i=0; i<m; ++i) {
        int a;
        pair<int, int> b;
        fin>>a>>b.F>>b.S;
        --a; --b.F;
        v[a].push_back(b);
    }

    int et[50001];
    bitset<50001> ka;

    for(int i=0; i<50001; ++i) {
        et[i]=1<<30;
    }

    vector< pair<int, int> > 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<int, int> 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(int i=0; i<v[q.F].size(); ++i) {
            int sk=v[q.F][i].F;
            int se=v[q.F][i].S+q.S;
            if(ka[sk] || se>=et[sk]) continue;
            j.push_back(make_pair(sk, se));
            push_heap(j.begin(), j.end(), comp);
        }
    }
    for(int i=1; i<n; ++i) {
        if(!ka[i]) fout<<0<<' ';
        else fout<<et[i]<<' ';
    }
    fout<<'\n';

}