#include <fstream>

using namespace std;

const int N = 5e4;
const int M = 25e4;
const int INF = 1 << 30;

pair<int, int> edges[M];
int cost[M], d[N + 1];

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

    int n, m, x, y, dist;
    in >> n >> m;
    for (int i = 0; i < m; ++i) {
        in >> x >> y >> dist;
        edges[i] = { x, y };
        cost[i] = dist;
    }
    for (int i = 2; i <= n; ++i)
        d[i] = INF;
    for (int i = 0; i < n - 1; ++i)
        for (int j = 0; j < m; ++j)
            if (d[edges[j].first] + cost[j] < d[edges[j].second])
                d[edges[j].second] = d[edges[j].first] + cost[j];
    bool ok = true;
    for (int i = 0; i < m; ++i)
        if (d[edges[i].first] + cost[i] < d[edges[i].second]) {
            ok = false;
            break;
        }
    if (ok)
        for (int i = 2; i <= n; ++i)
            out << d[i] << ' ';
    else
        out << "Ciclu negativ!";

    in.close();
    out.close();
    return 0;
}