#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;
}