#include <iostream>
#include <fstream>
#include <vector>

struct Edge {
    int from, to;
    int weight;
};

int main() {
    std::ifstream fileIn("bellmanford.in");
    std::ofstream fileOut("bellmanford.out");

    int nV, nE;
    fileIn >> nV >> nE;

    std::vector<Edge> edges(nE);

    for (Edge edge : edges) {
        fileIn >> edge.from >> edge.to >> edge.weight;
    }

    std::vector<int> dist(nV + 1, 2e9);

    dist[1] = 0;

    int aux;
    for (int i(0); i < nV - 1; i++) {
        for (Edge edge : edges) {
            aux = dist[edge.from] + edge.weight;
            if (aux < dist[edge.to]) {
                dist[edge.to] = aux;
            }
        }
    }

    bool check = true;
    for (Edge edge : edges) {
        aux = dist[edge.from] + edge.weight;
        if (aux < dist[edge.to]) {
            check = false;
            fileOut << "Ciclu negativ!";
            break;
        }
    }

    if (check) {
        for (int i(2); i <= nV; i++) {
            fileOut << dist[i] << ' ';
        }
    }

    fileIn.close();
    fileOut.close();
    return 0;
}