#include <fstream>
#include <vector>
#include <queue>

using namespace std;

const int N = 5e4;
const int INF = 1e9;

struct succesor {
    int vf, c;
};

int main() {
    ifstream in("bellmanford.in");
    ofstream out("bellmanford.out");
    int n, m;
    in >> n >> m;
    vector < vector <succesor>> l_s(n + 1);
    for (int i = 0; i < m; i++) {
        int x, y, c;
        in >> x >> y >> c;
        l_s[x].push_back((succesor){y, c});
    }
    in.close();
    vector <int> d(n + 1, INF);
    vector <int> nr_q(n + 1, 0);
    vector <bool> in_q(n + 1, false);
    queue <int> q;
    d[1] = 0;
    q.push(1);
    in_q[1] = true;
    nr_q[1] = 1;
    bool exista_ciclu_neg = false;
    while (!q.empty() && !exista_ciclu_neg) {
        int x = q.front();
        q.pop();
        in_q[x] = false;
        for (auto s : l_s[x]) {
            int y = s.vf, c = s.c;
            if (d[x] + c < d[y]) {
                d[y] = d[x] + c;
                if (nr_q[y] == n - 1) {
                    exista_ciclu_neg = true;
                    break;
                }
                if (!in_q[y]) {
                    in_q[y] = true;
                    q.push(y);
                    nr_q[y]++;
                }
            }
        }
    }
    if (exista_ciclu_neg) {
        out << "Ciclu negativ!";
    } else {
        for (int i = 2; i <= n; i++) {
            out << d[i] << " ";
        }
    }
    out << "\n";
    out.close();
    return 0;
}