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

#define MAX_N 50005

struct Edge {
    int to, cost;
    Edge(int to, int cost) : to{to}, cost{cost} {}
};

std::vector<Edge> adj[MAX_N];
int dist[MAX_N];
int in_queue_count[MAX_N];
bool in_queue[MAX_N];

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

    int n, m;
    fin >> n >> m;

    for (int i = 0; i < m; i++) {
        int u, v, cost;
        fin >> u >> v >> cost;
        adj[u].push_back(Edge(v, cost));
    }

    for (int i = 1; i <= n; i++) {
        dist[i] = std::numeric_limits<int>::max();
    }

    std::queue<int> q;
    dist[1] = 0;
    q.push(1);
    in_queue[1] = true;
    in_queue_count[1]++;

    bool negative_cycle = false;

    while (!q.empty() && !negative_cycle) {
        int current = q.front();
        q.pop();
        in_queue[current] = false;

        if (dist[current] == std::numeric_limits<int>::max()) {
            continue;
        }

        for (auto e : adj[current]) {
            if (dist[current] + e.cost < dist[e.to]) {
                dist[e.to] = dist[current] + e.cost;

                if (!in_queue[e.to]) {
                    q.push(e.to);
                    in_queue[e.to] = true;
                    in_queue_count[e.to]++;

                    if (in_queue_count[e.to] > n) {
                        negative_cycle = true;
                        break;
                    }
                }
            }
        }
    }

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