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

using namespace std;

ifstream f("bellmanford.in");
ofstream g("bellmanford.out");

const int NMAX = 50005;
const int INF = (1 << 30);

int N, M;
vector < pair < int, int > > G[NMAX];

pair < bool, vector < int > > bellmanFord(const int& src) {

    vector < bool > inQueue(N + 1, false);
    vector < int > dist(N + 1, INF), occurrences(N + 1, 0);
    queue < int > Q;

    dist[src] = 0;
    occurrences[src]++;
    inQueue[src] = true;

    Q.push(src);
    bool hasNegativeCycle{};

    while(!Q.empty() && !hasNegativeCycle) {

        const int node = Q.front();

        inQueue[node] = false;
        Q.pop();

        for(const pair < int, int >& neighbour : G[node]) {
            if(dist[node] + neighbour.second < dist[neighbour.first]) {

                dist[neighbour.first] = dist[node] + neighbour.second;

                if(inQueue[neighbour.first]) {
                    occurrences[neighbour.first]++;
                } else {
                    inQueue[neighbour.first] = true;
                    occurrences[neighbour.first]++;
                    Q.push(neighbour.first);
                }

                if(occurrences[neighbour.first] > N)
                    hasNegativeCycle = true;
            }
        }
    }

    return { hasNegativeCycle, dist };
}

int main() {

    f >> N >> M;

    while(M--) {
        int x, y, cost;
        f >> x >> y >> cost;

        G[x].push_back( { y, cost } );
    }

    auto sol = bellmanFord(1);

    if(sol.first)
        g << "Ciclu negativ!";
    else
        for(int i = 2;i <= N;++i)
            g << sol.second[i] << ' ';

    return 0;
}