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

#define NMAX 50009

class Task {
 public:
    void solve() {
        read_input();
        get_result();
    }

 private:
    int n;
    int m;
    int source;
    vector<pair<int, int>> adj[NMAX];

    void read_input() {
        source = 1;
        ifstream fin("bellmanford.in");
        fin >> n >> m;
        for (int i = 0; i < m; ++i) {
            int x, y, cost;
            fin >> x >> y >> cost;
            adj[x].push_back({cost, y});
        }
        fin.close();
    }

    void get_result() {
        vector<int> dist(n + 1, 1e9);
        dist[source] = 0;
        for (int i = 1; i < n; ++i) {
            for (int j = 1; j <= n; ++j) {
                for (auto &k : adj[j]) {
                    dist[k.second] = min(dist[k.second], dist[j] + k.first);
                }
            }
        }
        bool cycle = false;
        for (int j = 1; j <= n; ++j) {
            for (auto &k : adj[j]) {
                if (dist[k.second] > dist[j] + k.first) {
                    cycle = true;
                    break;
                }
            }
            if (cycle)
                break;
        }
        ofstream fout("bellmanford.out");
        if (cycle) {
            fout << "Ciclu negativ!";
        } else {
            for (int i = 1; i <= n; ++i)
                if (i != source)
                    fout << dist[i] << ' ';
        }
        fout.close();
    }
};

// Please always keep this simple main function!
int main() {
    // Allocate a Task object on heap in order to be able to
    // declare huge static-allocated data structures inside the class.
    Task *task = new Task();
    task->solve();
    delete task;
    return 0;
}