#include <iostream>
#include <vector>
#include <fstream>
#include <bitset>
#include <algorithm>
#include <utility>
#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 s,k;
    ifstream fin("dijkstra.in");
    ofstream fout("dijkstra.out");
    fin>>s>>k;
    vector< vector< pair<int, int> > > v(s);

    for(int i=0; i<k; ++i) {
        int a;
        pair<int, int> b;
        fin>>a>>b.F>>b.S;
        --a;
        --b.F;
        v[i].push_back(b);
    }

    bitset<50001> ka;
    vector<int> et(s);

    vector<pair<int, int> h;
    make_heap(h.begin(), h.end(), comp);
    h.push_back(make_pair(0, 0));
    push_heap(h.begin(), h.end(), comp);

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


}