#include <iostream>
#include <fstream>
#include <sstream>
#include <vector>
#include <deque>
#include <string>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <iterator>
 
using namespace std;

template<typename T>
void printV(const vector<T> &v) {
    for (size_t i = 0; i < v.size(); ++i) {
        cout << v[i] << " ";
    }
    cout << endl;
}

class bellmanford {
private:
    typedef vector<int> VI;
    typedef vector<int>::iterator VIIt;

    typedef pair<int, int> Edge;
    typedef map<Edge, int> CostFunc;
    typedef CostFunc::iterator CostFuncIt;

    typedef vector<VI> Graf;

    Graf g;
    CostFunc w;

    static const int INF = ~(1 << 31);

    void updateCost(int u, int v, int c) {
        Edge e(u, v);

        CostFuncIt it = w.find(e);
        if (it != w.end()) {
            if (it->second > c) {
                it->second = c;
            }
        } else {
            w.insert(pair<Edge, int>(e, c));
        }
    }

    void buildGraf(ifstream &in) {
        int n, m;

        in >> n >> m;

        Graf(n).swap(g);
        CostFunc().swap(w);

        for (int i = 0; i < m; ++i) {
            int x, y, c;

            in >> x >> y >> c;

            g[x - 1].push_back(y - 1);
            updateCost(x - 1, y - 1, c);
        }
    }

    /*
    void visitGraf(VI &vis, VI &d) {
        for (size_t i = 0; i < g.size(); ++i) {
            if (vis[i] == 0) {
                visitGraf(i, vis, d);
            }
        }
    }
    */

    void visitGraf(int i, VI &q, VI &d) {

        VI vis(g.size(), 0);
        VI nq;
       
        for (size_t i = 0; i < q.size(); ++i) {
            int u = q[i];

        //    cout << "u = " << u << endl;
            for (size_t j = 0; j < g[u].size(); ++j) {
                int v = g[u][j];

          //      cout << v << " - " << d[v] << endl;
                if (relax(u, v, d)) {
            //        cout << "relaxed " << d[v] << endl;
                    if (vis[v] == 0) {
              //          cout << "adding to the set\n";
                        vis[v] = 1;
                        nq.push_back(v);
                    } else {
                //        cout << "already in the set\n";
                    }
                } else {
                  //  cout << "didn't relax\n";
                }
            }
        }

        nq.swap(q);
        /*
        deque<int> q;
        q.push_back(i);
        vis[i] = 1;
        
        while (!q.empty()) {
            int u = q.front();
            q.pop_front();

            cout << "u = " << u << endl;
            for (size_t j = 0; j < g[u].size(); ++j) {
                int v = g[u][j];

                cout << v << " - " << d[v] << endl;
                if (relax(u, v, d)) {
                    cout << "relaxed " << d[v] << endl;
                    if (vis[v] == 0) {
                        cout << "adding to the set\n";
                        vis[v] = 1;
                        q.push_back(v);
                    } else {
                        cout << "already in the set\n";
                    }
                } else {
                    cout << "didn't relax\n";
                }
            }
        }
        */
    }

    bool relax(int u, int v, VI &d) {
        Edge e(u, v);
        int nd;

        if (d[u] == INF) {
            nd = INF;
        } else {
            nd = d[u] + w[e];
        }

        if (d[v] > nd) {
            d[v] = nd;
            return true;
        }
        return false;
    }
public:

    void func_bellmanford(ifstream &in, ofstream &out) {
        buildGraf(in);

        /*
        for (size_t i = 0; i < g.size(); ++i) {
            cout << i << ": ";
            for (size_t j = 0; j < g[i].size(); ++j) {
                cout << "(" << g[i][j] << " - " << w[Edge(i, g[i][j])] << ") ";
            }
            cout << endl;
        }
        */

        VI q(g.size(), 0);
        for (size_t i = 0; i < g.size(); ++i) {
            q[i] = i;
        }
        VI d(g.size(), ~(1 << 31));
        d[0] = 0;
        
        for (size_t i = 0; i < g.size() - 1; ++i) {
            visitGraf(0, q, d);
         //   printV<int>(d);
           // cout << "==================\n";
        }

        for (CostFuncIt i = w.begin(); i != w.end(); ++i) {
            int u = i->first.first;
            int v = i->first.second;

            if (d[v] > d[u] + i->second) {
                out << "Ciclu negativ!\n";
                return;
            }
        }

        /*
        for (size_t i = 0; i < d.size(); ++i) {
            if (d[i] == INF) {
                d[i] = 0;
            }
        }
        */
        copy(d.begin() + 1, d.end(), ostream_iterator<int>(out, " "));
    }
};

int main() {
    ifstream in("bellmanford.in");
    ofstream out("bellmanford.out");

    bellmanford x; x.func_bellmanford(in, out);
}