#include <bits/stdc++.h>
using namespace std;
vector <pair <int, int> > l[100];
int n, m, x, y, c;
vector <int> r, t(100);
ifstream fin("bellmanford.in");
#define cin fin
ofstream fout("bellmanford.out");
#define cout fout
void citire(){
    cin>>n>>m;
    for(int i=0; i<m; i++){
        cin>>x>>y>>c;
        l[x].push_back({y, c});
    }
    x=1;
}
void init(){
    r.resize(n+2, 1005);
    r[x]=0;
}
bool ok=1;
int main(){
    citire();
    init();

    for(int k=0; k<n; k++){
        for(int i=1; i<=n; i++){
            for(int j=0; j<l[i].size(); j++){
                //cout<<i<<' '<<l[i][j].first<<' '<<r[l[i][j].first]<<' '<<r[i]+l[i][j].second<<'\n';
                if(r[l[i][j].first]>r[i]+l[i][j].second){
                    //cout<<i<<' '<<l[i][j].first<<'\n';
                    r[l[i][j].first]=r[i]+l[i][j].second;

                }
            }
        }
    }
    bool ok=1;
    for(int i=1; i<=n; i++){
            for(int j=0; j<l[i].size(); j++){
                //cout<<i<<' '<<l[i][j].first<<' '<<r[l[i][j].first]<<' '<<r[i]+l[i][j].second<<'\n';
                if(r[l[i][j].first]>r[i]+l[i][j].second){
                    //cout<<i<<' '<<l[i][j].first<<'\n';
                    ok=0;

                }
            }
        }

    if(ok) for(int i=2; i<=n; i++) cout<<r[i]<<' ';
    else cout<<"Ciclu negativ!";
    return 0;
}