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

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> *vertices = new std::vector<Edge>[nV + 1];

    std::vector<int> visit(nV + 1, 0);

    for (int i(0); i < nE; i++) {
        Edge auxEdge;
        fileIn >> auxEdge.from >> auxEdge.to >> auxEdge.weight;
        vertices[auxEdge.from].push_back(auxEdge);
    }

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

    std::list<int> myQ;

    myQ.push_back(1);
    dist[1] = 0;

    int aux;
    bool isOk = true;
    while (!myQ.empty()) {
        aux = myQ.front();
        myQ.pop_front();

        visit[aux]++;

        if (visit[aux] == nV) {
            isOk = false;
            break;
        }

        for (Edge edge : vertices[aux]) {
            if (edge.weight + dist[edge.from] < dist[edge.to]) {
                dist[edge.to] = edge.weight + dist[edge.from];
                myQ.push_back(edge.to);
            }
        }
    }

    if (isOk) {
        for (int i(2); i <= nV; i++) {
            fileOut << dist[i] << ' ';
        }
    } else {
        fileOut << "Ciclu negativ!";
    }

    delete[] vertices;
    fileIn.close();
    fileOut.close();
    return 0;
}