#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#define nmax 50009
#define INF 999999
using namespace std;
int n,m,sol[nmax],v[nmax],ok[nmax];
queue<int> q;
vector<pair <int,int> >G[nmax];
inline void bf(){
 int i,k,j,g=1;
 for(i=1;i<=n;i++)
    sol[i]=INF;
 sol[1]=0;
 q.push(1);
 ok[1]=1;
 long long p=0,kk=n*m;
 while(!q.empty()&&g){
    k=q.front();
    q.pop();
    ok[k]=0;
    for(i=0;i<G[k].size();i++)
    if((sol[G[k][i].first] > sol[k]+G[k][i].second)){
            v[G[k][i].first]++;
            if(v[G[k][i].first]>n) g=0;
            p++;
            if(!ok[G[k][i].first]){
                    ok[G[k][i].first]=1;
        q.push(G[k][i].first);}
        sol[G[k][i].first]= sol[k]+G[k][i].second;
    }
 }
}
inline void Afis(){
    for(int i=1;i<=n;i++)
        if(v[i]>n&&sol[i]<0) {cout<<"Ciclu negativ!";return;}
    for(int i = 2;i<=n;i++)
        cout << sol[i]<<' ';
}
int main(){
    int x,y,cost;
    freopen("bellmanford.in","r",stdin);
    freopen("bellmanford.out","w",stdout);
    scanf("%d%d",&n,&m);
    while(m--){
        scanf("%d%d%d",&x,&y,&cost);
        G[x].push_back(make_pair(y,cost));
    }
    bf();
    Afis();
    return 0;
}