#include <bits/stdc++.h>
#define MAX 50005
#define INFINIT 50005000
using namespace std;
ifstream fin ("bellmanford.in");
ofstream fout("bellmanford.out");
typedef pair <int, int> pairINT;

int n,Dist[MAX],Viz[MAX];
vector <pairINT> Nod[MAX];
bool negativ;

void read();
void BellmanFord();
void ans();

int main(){
    read();
    BellmanFord();
    ans();
    return 0;
}
void BellmanFord(){
    int i,j,q;
    for(i=2;i<=n;++i)
        Dist[i]=INFINIT;

    for(q=1;q<n+20;++q){
        for(i=1;i<=n;++i){
            for(auto it:Nod[i]){
                if(Dist[i]+it.first<Dist[it.second])
                    Dist[it.second]=Dist[i]+it.first;
            }
        }
    }
    for(i=1;i<=n;++i){
        for(auto it:Nod[i]){
            if(Dist[i]+it.first<Dist[it.second]){
                negativ=1;
                return;
            }
        }
    }
}
void read(){
    int i,m,x,y,c;
    fin>>n>>m;
    for(i=0;i<m;++i){
        fin>>x>>y>>c;
        Nod[x].push_back(make_pair(c,y));
//        Nod[y].push_back(make_pair(c,x));
    }
}
void ans(){
    int i;
    if(negativ){
        fout<<"Ciclu negativ!";
        return;
    }

    for(i=2;i<=n;++i){
        fout<<Dist[i]<<' ';
    }
}