#include <bits/stdc++.h>
#define ll long long
#define pb push_back
using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
const int mod = 1e9 + 7;
ll inf=1e16;
ll n,m,i,j,k,t;
ll dis[100005];
vector<tuple<ll,ll,ll>> e;
int32_t main(){
    //ios::sync_with_stdio(0); cin.tie(0);
    fin>>n>>m;
    for(i=1;i<=m;i++){
        ll x,y,z;
        fin>>x>>y>>z;
        e.pb(make_tuple(x,y,z));
    }
    ll ans=-1;
    dis[1]=0;
    for(i=2;i<=n;i++){
        dis[i]=inf;
    }
    for(i=1;i<=n;i++){
        for(auto q:e){
            ll x,y,z;
            tie(x,y,z)=q;
            if(dis[y]>dis[x]+z){
                ans=i;
                dis[y]=dis[x]+z;
            }
        }
    }

    if(ans==n) fout<<"Ciclu negativ!";
    else{
        for(i=2;i<=n;i++) fout<<dis[i]<<" ";
    }
    return 0;
}