///BELLMANFORD CDI 05.01
#include <iostream>
#include <fstream>
#include <vector>
#include <list>
#include <queue>
#include <limits>

using namespace std;

typedef pair<int, int> Node;

const int MAXINT = numeric_limits<int>::max();

void bellmanFord(vector<list<Node> >& adjList, vector<int>& minCost, bool& isNegCyc) {
    queue<int> q;
    q.push(0);

    minCost[0] = 0;

    vector<bool> inq(adjList.size(), false);
    inq[0] = true;

    vector<int> numRel(adjList.size(), 0);
    ++numRel[0]; ///?????

    isNegCyc = false;

    int current;
    list<Node>::iterator it;
    while(!q.empty()) {
        current = q.front();
        q.pop();

        inq[current] = false;
        for(it = adjList[current].begin(); it != adjList[current].end(); ++it) {
            if(it -> second + minCost[current] < minCost[it -> first] && !inq[it -> first]) {
                minCost[it -> first] = it -> second + minCost[current];
                ++numRel[it -> first];

                if(numRel[it -> first] >= adjList.size()) {
                    isNegCyc = true;
                    return;
                }

                inq[it -> first] = true;
                q.push(it -> first);
            }
        }
    }
}

int main() {
    ifstream inStr("bellmanford.in");
    ofstream outStr("bellmanford.out");

    int N, M;
    inStr >> N >> M;

    vector<list<Node> > adjList(N);

    int from, to, cost;
    for(int i=0; i<M; ++i) {
        inStr >> from >> to >> cost;
        adjList[--from].push_back(Node(--to, cost));
    }

    bool isNegCyc;
    vector<int> minCost(N, MAXINT);
    bellmanFord(adjList, minCost, isNegCyc);

    if(isNegCyc)
        cout << "Ciclu negativ!";
    else
        for(int i=1; i<N; ++i)
            if(minCost[i] == MAXINT)
                cout << 0 << ' ';
            else
                cout << minCost[i] << ' ';
    cout << '\n';

    return 0;
}