#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#define nmax 50009
#define INF 999999
using namespace std;
int n,m,sol[nmax],v[nmax],g=1;
queue<int> q;
vector<pair <int,int> >G[nmax];
inline void soll(){
 int i,k;
 for(i=1;i<=n;i++)
    sol[i]=INF;
 sol[1]=0;
 q.push(1);
 while(!q.empty()&&g){
    k=q.front();
    q.pop();
    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;
        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(!g) {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));
    }
    soll();
    Afis();
    return 0;
}