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

using namespace std;

const int INF = numeric_limits<int>::max();

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

    int N, M;
    fin >> N >> M;

    vector<vector<pair<int, int>>> adj(N + 1);
    for (int i = 0; i < M; ++i) {
        int x, y, c;
        fin >> x >> y >> c;
        adj[x].emplace_back(y, c);
    }

    vector<int> dist(N + 1, INF);
    dist[1] = 0;

    for (int i = 1; i <= N - 1; ++i) {
        for (int u = 1; u <= N; ++u) {
            for (const auto& edge : adj[u]) {
                int v = edge.first;
                int c = edge.second;
                if (dist[u] != INF && dist[u] + c < dist[v]) {
                    dist[v] = dist[u] + c;
                }
            }
        }
    }

    bool hasNegativeCycle = false;
    for (int u = 1; u <= N; ++u) {
        for (const auto& edge : adj[u]) {
            int v = edge.first;
            int c = edge.second;
            if (dist[u] != INF && dist[u] + c < dist[v]) {
                hasNegativeCycle = true;
                break;
            }
        }
        if (hasNegativeCycle) break;
    }

    if (hasNegativeCycle) {
        fout << "Ciclu negativ!";
    } else {
        for (int i = 2; i <= N; ++i) {
            fout << dist[i] << " ";
        }
    }

    return 0;
}