#include <bits/stdc++.h>
#define Intro ios::sync_with_stdio(0), cin.tie(0)
#define ll long long
using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
int const N = 5e4 + 4;
vector<pair<int, int>> neighbours[N];
vector<int> costs(N, INT_MAX), cnt_in_queue(N);
bitset<N> in_queue;
bool negative_cicle = false;
int total_nodes;

void find_costs() {
    queue<int> nodes;
    nodes.push(1);
    while (!nodes.empty() and !negative_cicle) {
        int node = nodes.front();
        nodes.pop();
        in_queue[node] = false;
        for (auto itr : neighbours[node]) {
            int neighbour = itr.first, curr_cost = itr.second;
            if (costs[neighbour] > costs[node] + curr_cost) {
                costs[neighbour] = costs[node] + curr_cost;
                if (!in_queue[neighbour]) {
                    if (cnt_in_queue[neighbour] > total_nodes) {
                        negative_cicle = true;
                    }
                    nodes.push(neighbour);
                    in_queue[neighbour] = true;
                    cnt_in_queue[neighbour]++;
                }
            }
        }
    }
}

int main() {
    int edges; fin >> total_nodes >> edges;
    for (int i = 1; i <= edges; ++i) {
        int src, dest, cost;
        fin >> src >> dest >> cost;
        neighbours[src].push_back({dest, cost});
    }
    costs[1] = 0;
    find_costs();
    if (negative_cicle) {
        fout << "Ciclu negativ!";
    } else {
        for (int i = 2; i <= total_nodes; ++i) {
            fout << costs[i] << ' ';
        }
    }
    return 0;
}