#include <bits/stdc++.h>
using namespace std;
#define INF 1e9
vector<pair<int,int>> graf[60005]; /// unul este pentru nodul asociat muchiei iar celalata locatie este alocata pentru cost
int d[60005];
int main(void){
    ofstream cout("dijkstra.out");
    ifstream cin("dijkstra.in");
    int n,m;
    cin >>  n >> m;
    for(int i = 1;i<=m;i++){
        int x, y, z;
        cin >> x >> y >> z;
        graf[x].push_back({z,y});
    }
    for(int i = 2;i<=n;i++){
        d[i] = INF;
    }
    set<pair<int,int>> st;
    st.insert({0,1});
    while(!st.empty()){
        int k = st.begin() -> second;
        st.erase(st.begin());
        for(auto nod: graf[k]){
            int vec = nod.second;
            int cost = nod.first;
            if(d[vec] > d[k] + cost){ /// acutalizam
                st.erase({d[vec],vec});
                d[vec] = d[k] + cost;
                st.insert({d[vec], vec});
            }
        }
    }
    for(int i = 2;i<=n;i++){
        if(d[i] != INF){
            cout << d[i] << ' ';
        }else cout << 0 << ' ';
    }
}