#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 50005;

int n,m;

bool cicluNegativ;

struct Muchie{
    int u, v, cost;
};

vector <Muchie> muchii;

vector <long long> BellmanFord(int start, vector <int> &tata){
    vector <long long> d(n+1, 1e9);

    d[start]=0;
    for (int i=1;i<=n-1;i++){
        for (auto m : muchii){
            if (d[m.u]!=1e9){
                if (d[m.u] + m.cost < d[m.v]){
                    d[m.v]=d[m.u]+m.cost;
                    tata[m.v]=m.u;
                }
            }
        }
    }

    for (auto m : muchii){
        if (d[m.u]!=1e9 && d[m.u] + m.cost < d[m.v]){
            cicluNegativ=true;
        }
    }

    return d;
}

int main(){
    f>>n>>m;
    for (int i=1;i<=n;i++){
        int nod1, nod2, cost;
        f>>nod1>>nod2>>cost;
        muchii.push_back({nod1, nod2, cost});
    }

    vector <int> tata(n+1, 0);
    vector<long long> dist = BellmanFord(1, tata);

    if (cicluNegativ==true) g<<"Ciclu negativ!"<<'\n';
    else{
        for (int i=2;i<=n;i++){
            if (dist[i]==1e9) g<<0<<" ";
            else g<<dist[i]<<" ";
        }
    }
}