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

using namespace std;

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


int n;

struct edge {
    int x;
    int y;
    int c;
};

int main() {
    int m;

    in >> n >> m;

    vector<edge> edges;
    vector<int> d(n + 1, 1000000000);

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

        in >> x >> y >> c;

        edge e = {x, y, c};

        edges.push_back(e);

        if (x == 1) {
            d[y] = c;
        }
    }

    for (int i = 0; i < n - 2; ++i) {
        for (vector<edge>::iterator e = edges.begin(); e != edges.end(); ++e) {
            if (d[e->y] > d[e->x] + e->c) {
                d[e->y] = d[e->x] + e->c;
            }
        }
    }

    for (vector<edge>::iterator e = edges.begin(); e != edges.end(); ++e) {
        if (d[e->y] > d[e->x] + e->c) {
            out << "Ciclu negativ!\n";
        }
    }

    for (int i = 2; i <= n; ++i) {
        out << d[i] << ' ';
    }
    out << '\n';

    return 0;
}