#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <bitset>
using namespace std;

#define F first
#define S second

bool comp(const pair<int, int> & a, const pair<int, int> & b) {
    return a.S > b.S;
}

int main() {
    int s,k;
    cin>>s>>k;
    vector< vector< pair<int, int> > > v(s);
    for(int i=0; i<k; ++i) {
        int a;
        pair<int, int> b;
        cin>>a>>b.F>>b.S;
        --b.F;
        v[a-1].push_back(b);
    }
     
    
    vector<int> et(s+1);
    for(int i=0; i<s+1; ++i) {
        et[i]=1<<30; 
    }
    bitset<50001> ka;
    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);
    
    int w=0;
    for(;j.size()>0;) {
        pop_heap(j.begin(), j.end(), comp);
        pair<int, int> q=j.back(); 
        j.pop_back();
        if(ka[q.F]==1) {
            continue;
        }
        ++w;
        if(q.F>=et.size() || q.F>=50001) {
            return -1;
        }
        ka[q.F]=1;
        et[q.F]=q.S;
        for(int i=0; i<v[q.F].size(); ++i) {
            int uk=v[q.F][i].F;
            int ue=q.S+v[q.F][i].S;
            if(uk>=et.size() || uk>=50001) {
                return -1;
            }
            if(ka[uk] || ue >= et[uk]) {
                continue;
            }
            et[uk]=ue;
            j.push_back(make_pair(uk, ue));
            push_heap(j.begin(), j.end(), comp);
        }
    } 
    for(int i=1; i<s; ++i) {
        if(ka[i]==0) cout<<0<<' ';
        else 
        cout<<et[i]<<' ';
    }
    cout<<'\n';
}