#include <bits/stdc++.h>
using namespace std;
ifstream fin("dijkstra.in");
#define cin fin
ofstream fout("dijkstra.out");
#define cout fout
vector <pair<int, int> > l[50005];
bitset <50005> viz;
set <pair<int, int> > s;
vector <int> r;
int n, m, x, y, c;
int main(){
    cin>>n>>m;
    for(int i=0; i<m; i++){
        cin>>x>>y>>c;
        l[x].push_back({y, c});
    }
    s.insert({0, 1});
    r.resize(n+1, 2147483647);
    r[0]=0;
    while(!s.empty()){
        int nod=s.begin()->second;
        s.erase(s.begin());
        if(!viz[nod]){
            viz[nod]=1;
            int cost, vc;
            for(int i=0; i<l[nod].size(); i++){
                vc=l[nod][i].first;
                cost=l[nod][i].second;
                if(!viz[vc] && r[vc-1]>r[nod-1]+cost){
                    r[vc-1]=r[nod-1]+cost;
                    s.insert({r[vc-1], vc});
                }
            }
        }
    }
    for(int i=1; i<r.size()-1; i++) cout<<r[i]<<' ';
    return 0;
}