#include <bits/stdc++.h>
using namespace std;

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

vector<pair<int,int> >G[50005];
queue<int> q;

int viz[50005], a[50005],fv[50005], n,m;

void bellmanford(int sursa){

    for(int i=1;i<=n;i++)
        a[i]=INT_MAX-1000;

    a[sursa]=0;
    q.push(sursa);

    while(!q.empty()){

        int coada=q.front();
        viz[coada]=0;

        for(int i=0;i<G[coada].size();i++){

            int vecin=G[coada][i].first;
            int cost=G[coada][i].second;

            if(a[vecin]>a[coada]+cost){
                a[vecin]=a[coada]+cost;

                if(viz[vecin]==0){

                    viz[vecin]=1;
                    fv[vecin]++;
                    q.push(vecin);

                    if(fv[vecin]==n){

                        g<<"Ciclu negativ!";

                        return;
                    }
                }
            }
        }

        q.pop();

    }

    for(int i=2;i<=n;i++)

        g<<a[i]<<" ";

}

int main(){

    f>>n>>m;

    for(int i=1;i<=m;i++){

        int x,y,c;
        f>>x>>y>>c;
        G[x].push_back({y,c});

    }

    bellmanford(1);

    return 0;

}