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

struct Node {
    int idx;
    int cost;
    bool operator<(const Node& node) const {
        return this->cost > node.cost;
    }
};

const int INF = 0x3f3f3f3f;
int n, m;
vector<vector<Node>> nodes;
int res[50005], freq[50005];
bool hasNegativeCycle;

void bellmanFord() {
    priority_queue<Node> queue;
    queue.push({1, 0});
    res[1] = 0;
    while (!queue.empty()) {
        const int currentNode = queue.top().idx;
        queue.pop();
        if (freq[currentNode] > n) {
            hasNegativeCycle = true;
            return;
        }
        for (const Node& neighbour : nodes[currentNode]) {
            if (res[currentNode] + neighbour.cost < res[neighbour.idx]) {
                res[neighbour.idx] = res[currentNode] + neighbour.cost;
                freq[currentNode]++;
                queue.push({neighbour.idx, res[neighbour.idx]});
            }
        }
    }
}

int main() {
    ifstream input("bellmanford.in");
    ofstream output("bellmanford.out");
    input >> n >> m;
    nodes = vector<vector<Node>>(n + 1);

    for (int q = 0; q < m; q++) {
        int i, j, c;
        input >> i >> j >> c;
        nodes[i].push_back({j, c});
    }

    memset(res, INF, sizeof res);
    bellmanFord();

    if (hasNegativeCycle) {
        output << "Ciclu negativ!";
    } else {
        for (int q = 2; q <= n; q++) {
            output << res[q] << " ";
        }
    }
    return 0;
}