#include <bits/stdc++.h>
using namespace std;

ifstream in("dijkstra.in");
ofstream out("dijkstra.out");

class Graf{
    int nr_noduri, nr_muchii;
    const int inf = INT_MAX;
public:


    //lista drumurilor minime de la un nod dat
    void BellmanFord(const int start);
};



void Graf ::BellmanFord(const int start) {
    in >> nr_noduri >> nr_muchii;
    vector<pair<int, int>> lista_muchii[nr_noduri+1];
    vector<int> d(nr_noduri+1,inf);
    d[start] = 0;
    for(int i = 1; i <= nr_muchii; ++i){
        int x,y,cost;
        in >> x >> y >> cost;
        lista_muchii[x].push_back({y,cost});

    }

            //relaxam de N-1 ori nodurile
    for(int j = 1; j <= nr_noduri-1; ++j){
        for(int i = 1; i <= nr_noduri; ++i)
            for(auto val : lista_muchii[i])
            {
                if(d[val.first] > d[i] + val.second)
                    d[val.first] = d[i] + val.second;
            }
    }
    for(int i = 1; i <= nr_noduri; ++i)
        if(d[i])
            out << d[i] << " ";

}

int main() {

    Graf g;
    g.BellmanFord(1);
    return 0;
}