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

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

    std::vector<pair<int,int>> muchii[50006];

    int main() {
        int n,m;
        f>>n>>m;
        for (int i=0;i<m;i++) {
            int x,y,cost;
            f>>x>>y>>cost;
            muchii[x-1].emplace_back(y-1,cost);
        }
        int updates[50006]={0};
        int distance[50006];
        for (int i=0;i<n;i++) {
            distance[i]=100000000;
        }
        distance[0]=0;
        queue<int> toCheck;
        toCheck.push(0);
        while (!toCheck.empty()){
            int x=toCheck.front();
            toCheck.pop();
            for (auto [y,cost]:muchii[x]) {
                if (distance[x]+cost<distance[y]) {
                    toCheck.push(y);
                    updates[y]+=1;
                    if (updates[y]>n) {
                        cout<<"Ciclu negativ!";
                        return 0;
                    }
                    distance[y]=distance[x]+cost;
                }
            }
        }
        for (int i=0;i<n;i++) {
            for (int x=0;x<n;x++) {
                for (auto [y,cost]:muchii[x]) {
                    if (distance[x]+cost<distance[y]) {
                        g<<"Ciclu negativ!";
                        return 0;
                    }
                }
            }
        }
        for (int i=1;i<n;i++) {
            g<<distance[i]<<" ";
        }

    }