#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;

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

const int INF = 1e9;
vector<vector<pair<int,int>>> adj;

bool spfa(int s, vector<int>& d) {
    int n = adj.size();
    d.assign(n, INF);
    vector<int> cnt(n, 0);
    vector<bool> inqueue(n, false);
    queue<int> q;

    d[s] = 0;
    q.push(s);
    inqueue[s] = true;

    while (!q.empty()) {
        int v = q.front();
        q.pop();
        inqueue[v] = false;

        for (auto edge : adj[v]) {
            int to = edge.first;
            int len = edge.second;

            if (d[v] + len < d[to]) {
                d[to] = d[v] + len;
                if (!inqueue[to]) {
                    q.push(to);
                    inqueue[to] = true;
                    cnt[to]++;
                    if (cnt[to] > n)
                        return false;
                }
            }
        }
    }
    return true;
}

int N, M;

int main()
{
    fin >> N >> M;
    adj.assign(N + 1, vector<pair<int,int>>());

    for (int i = 0; i < M; i++) {
        int a, b, c;
        fin >> a >> b >> c;
        adj[a].push_back({b, c});
    }

    vector<int> dist;
    bool noNegativeCycle = spfa(1, dist);

    if (!noNegativeCycle) {
        fout << "Ciclu negativ!\n";
    } else {
        for (int i = 2; i <= N; i++) {
            if (dist[i] == INF)
                fout << 0 << " ";
            else
                fout << dist[i] << " ";
        }
        fout << "\n";
    }
    return 0;
}