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

#define MAX_N 105

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_c[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_c[1]++;

    bool neg = false;
    while (!q.empty() && !neg) {
        auto current = q.front();
        q.pop();
        in_queue[current] = false;

        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_c[e.to]++;

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

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

        fout << "\n";
    }
}