#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <set>

using namespace std;

int main() {
    int n, k, nl, q, x, y, c, dst, d2, m;
    const int INF = 50000001;
    long long sum;
    
    
    ifstream myfile;
    myfile.open ("dijkstra.in");
    myfile>>n>>m;
    //myfile>>m;
    vector <vector<pair<int, int> > > ad(n);
    vector <int> d(n, INF);
    //vector <int> viz(n, 0);
    //viz[0] = 1;
    d[0] = 0;
    set <pair<int, int> > st;
    set <pair<int, int> > ::iterator it;
    st.insert(make_pair(0, 0));
    
    for (int i = 0; i < m; i++) {
        myfile>>x>>y>>c;
        ad[x-1].push_back(make_pair(y-1, c));
    }
    myfile.close();
    
    while (!st.empty()) {
        it = st.begin();
        dst = it->first;
        st.erase(it);
        x = it->second;
        for (int i = 0; i < ad[x].size(); i++) {
            y = ad[x][i].first;
            d2 = ad[x][i].second + dst;
            if (d[y] > d2) {
                d[y] = d2;
                st.insert(make_pair(d[y], y));
            }
        }
    }
    
    ofstream f2;
    f2.open ("dijkstra.out");
     for (int i = 1; i < n; i++) {
        if (d[i] == INF)
            d[i] = 0;
        f2<<d[i]<<" ";
     }
        f2<<endl;
    f2.close();
       
    return 0;
}