#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <string>

#define NMAX 50010
#define oo (1 << 30)

using namespace std;

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

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

    void read_input() {
        ifstream fin("bellmanford.in");
        fin >> n >> m;
        d.resize(n + 1);
        p.resize(n + 1);
        source = 1;

        for (int i = 1; i <= m; ++i) {
            int x, y ,c;
            fin >> x >> y >> c;
            adj[x].push_back({y, c});
        }
        fin.close();
    }

    void get_result() {
        ofstream fout("bellmanford.out");
        if (BellmanFord(source, d, p)) {
            fout << "Ciclu negativ!";
        } else {
            print_output();
        }
    }

    bool BellmanFord(int source, vector<int> &d, vector<int> &p) {
        vector<int> used(n + 1, 0);
        
        for (int i = 1; i <= n; ++i) {
            d[i] = oo;
            p[i] = -1;
        }

        p[source] = 0;
        d[source] = 0;
        q.push(source);

        while(!q.empty()) {
            int node = q.front();
            q.pop();

            ++used[node];
            if (used[node] == n) {
                return true;
            }

            for (auto &edge : adj[node]) {
                int neighbor = edge.first;
                int cost_edge = edge.second;

                if (d[node] + cost_edge < d[neighbor]) {
                    d[neighbor] = d[node] + cost_edge;
                    p[neighbor] = node;
                    q.push(neighbor);
                }
            }
        }

        return false;
    }

    void print_output() {
        ofstream fout("bellmanford.out");
        for (int i = 2; i < d.size(); ++i) {
            fout << d[i] << " ";
        }
        fout << "\n";
        fout.close();
    }
};

int main() {
    Task *task = new Task();
    task->solve();
    delete task;

    return 0;
}