#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <fstream>
using namespace std;
#define ll long long int
bool comp(const pair<int, int> & a, const pair<int, int> & b) {
    return a.second>b.second;
}
int main() {
    ll n,m;

    ifstream fin("dijkstra.in");
    ofstream fout("dijkstra.out");
    fin>>n>>m;
    vector< vector< pair<int, int> > > kaaret(n);
    for(int i=0; i<m; ++i) {
        pair<int, int> lol;
        ll a;
        fin>>a>>lol.first>>lol.second;
        --lol.first;
        kaaret[a-1].push_back(lol); 
    }
    vector< pair<int, int> > q;
    make_heap(q.begin(), q.end(), comp);
    q.push_back(make_pair(0, 0));
    vector<int> kaydyt(n);
    vector<int> et(n);
    for(int i=0; i<kaydyt.size(); ++i) {
        et[i]=1<<30;
    } int ma=0;
    for(;q.size()>0;) {
        pop_heap(q.begin(), q.end(), comp);
        
        pair<int, int> w=q.back();
        //cout<<w.first<<'\n';
        //cout<<q.size()<<'\n';
        q.pop_back();
        if(kaydyt[w.first]) {
            goto ohi;
        }
        et[w.first]=w.second;
        kaydyt[w.first]=1;
        ++ma;
        if(m==n-1) {
            goto ohi2;
        }
        for(int i=0; i<kaaret[w.first].size(); ++i) {
            if(kaydyt[kaaret[w.first][i].first]) {
                continue;
            }
            if(et[kaaret[w.first][i].first]<=w.second+kaaret[w.first][i].second) {
                continue;
            }
            q.push_back(make_pair(kaaret[w.first][i].first, w.second+kaaret[w.first][i].second));
            push_heap(q.begin(), q.end(), comp);
        }
ohi:;
    }
ohi2:;
     for(int i=1; i<et.size(); ++i) {
         if(et[i]==1<<30) {
             fout<<0<<'\n';
         }
         else 
         fout<<et[i]<<' ';
     }
}