#include <iostream>
#include <algorithm>
#include <vector>
#include <fstream>
#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;
    ifstream fin("dijkstra.in");
    ofstream fout("dijkstra.out");
    fin>>s>>k;
    vector< vector< pair<int, int> > > v(s+1);
    for(int i=0; i<k; ++i) {
        int a;
        pair<int, int> b;
        fin>>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;) {
        pair<int, int> q=j.front(); 
        pop_heap(j.begin(), j.end(), comp);
        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;
    //    if(q.F >= v.size()) return -1;
        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) fout<<0<<' ';
        else 
        fout<<et[i]<<' ';
    }
    fout<<'\n';
}