#include <iostream>
#include <algorithm>
#include <utility>
#include <fstream>
#include <vector>
#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< vector< pair<int, int> > > v(n);
    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);
    }
    bitset<50000> kaydyt;
    vector<int> et(n);
    for(int i=0; i<n; ++i) et[i]=1<<30;

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