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

using namespace std;

class InParser {
private:
    FILE *fin;
    char *buff;
    int sp;

    char read_ch() {
        ++sp;
        if (sp == 4096) {
            sp = 0;
            fread(buff, 1, 4096, fin);
        }
        return buff[sp];
    }

public:
    InParser(const char* nume) {
        fin = fopen(nume, "r");
        buff = new char[4096]();
        sp = 4095;
    }

    InParser& operator >> (int &n) {
        char c;
        while (!isdigit(c = read_ch()) && c != '-');
        int sgn = 1;
        if (c == '-') {
            n = 0;
            sgn = -1;
        } else {
            n = c - '0';
        }
        while (isdigit(c = read_ch())) {
            n = 10 * n + c - '0';
        }
        n *= sgn;
        return *this;
    }

    InParser& operator >> (long long &n) {
        char c;
        n = 0;
        while (!isdigit(c = read_ch()) && c != '-');
        long long sgn = 1;
        if (c == '-') {
            n = 0;
            sgn = -1;
        } else {
            n = c - '0';
        }
        while (isdigit(c = read_ch())) {
            n = 10 * n + c - '0';
        }
        n *= sgn;
        return *this;
    }
};

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