#include <bits/stdc++.h>



std::ifstream input ("bellmanford.in");

std::ofstream output("bellmanford.out");



#define num     long long

#define INF     20000000000000005



num N, M;

std::vector <num> dist, times;

std::vector <bool> inQueue;

std::vector <std::vector <std::pair <num, num>>> ADC;

inline void addEdge(num x, num y, num w) {

    ADC[x].push_back({y, w});

}



std::queue <num> queue;

bool hasNegativeCycle() {

    while (!queue.empty()) queue.pop();

    for (int i=0; i<N; ++i)

        dist[i] = INF;

    dist[0] = 0;

    queue.push(0);



    while (!queue.empty()) {

        num front = queue.front();

        queue.pop();



        inQueue[front] = false;

        ++ times[front];

        if (times[front] == N) return true;



        for (auto it:ADC[front])

            if (dist[it.first] > dist[front] + it.second) {

                dist[it.first] = dist[front] + it.second;

                if (!inQueue[it.first])

                    inQueue[it.first] = true, queue.push(it.first);

            }

    }   return false;

}



int main()

{

    num T;  T = 1;

    while (T--) {

        input >> N >> M;

        ADC.clear(), dist.clear(), inQueue.clear(), times.clear();

        ADC.resize(N), dist.resize(N, 0), times.resize(N, 0), inQueue.resize(N, false);



        for (num i=0, x, y, z; i<M; ++i)

            input >> x >> y >> z, addEdge(--x, --y, z);

        if (hasNegativeCycle())

            output << "Ciclu negativ!\n";

        else {

            for (int i=1; i<N; ++i)

                output << dist[i] << ' ';

        }

    }



    return 0;

}