#include <fstream>
#include <vector>
using namespace std;
ifstream cin("dijkstra.in");
ofstream cout("dijkstra.out");
const int nmax = 5e4 + 1 , oo = 1e9;
class Tree{
private:
    int tr[4*nmax];
    int helper(int f , int s){
        if(f == -1) return s;
        if(s == -1) return f;
        if(f < s) return f;
        return s;
    }
public:
    void build(int node , int l , int r){
        if(l == r){
            if(l == 1) tr[node] = 0;
            else tr[node] = oo;
        }else{
            int mid = l + (r-l)/2;
            build(node<<1,l,mid) , build(node<<1|1,mid+1,r);
            tr[node] = helper(tr[node<<1],tr[node<<1|1]);
        }
    }
    void update_value(int node , int l , int r , int &poz ,const int &sup_better){
        if(l == r) tr[node] = min(tr[node],sup_better);
        else{
            int mid = l + (r-l)/2;
            if(poz <= mid) update_value(node<<1,l,mid,poz,sup_better);
            else update_value(node<<1|1,mid+1,r,poz,sup_better);
            tr[node] = helper(tr[node<<1],tr[node<<1|1]);
        }
    }
    pair<int,int>getter(int node , int l , int r){
        if(l == r) return make_pair(tr[node],l);
        int mid = l + (r-l)/2;
        if(tr[node<<1] == tr[node]) return getter(node<<1,l,mid);
        return getter(node<<1|1,mid+1,r);
    }
};
vector <pair<int,int>> g[nmax];
signed main() {
    Tree tree = Tree();
    int n , m , a , b , c;
    cin >> n >> m;
    vector <int> ans(n,0);
    for(int i = 1 ; i <= m ; ++i){
        cin >> a >> b >> c;
        g[a].push_back(make_pair(b,c));
    }
    tree.build(1,1,n);
    for(int i = 1 ; i <= n ; ++i){
        pair<int,int> x = tree.getter(1,1,n);
        if(x.first == oo) break;
        ans[x.second] = x.first;
        for(auto it : g[x.second]){
            tree.update_value(1,1,n,it.first,x.first+it.second);
        }
        tree.update_value(1,1,n,x.second,-1);
    }
    for(int i = 2 ; i <= n ; ++i) cout << ans[i] << ' ';
    return 0;
}