#include <iostream>
#include <cstdio>
#include <vector>
#define nmax 50009
using namespace std;
int n,m,P[nmax],sol[nmax],v[nmax];
vector<pair <int,int> >G[nmax];
inline void Create(){
 for(int i = 1; i<=nmax;i++)
    sol[i]=3000000;
}
inline void bfs(){
 int i,k,j;
 sol[1]=0;
 P[1] = 1;
 k=1;
 for(i=1;i<=k;i++)
    for(j = 0; j < G[P[i]].size();j++)
        if(sol[G[P[i]][j].first]==3000000 || sol[G[P[i]][j].first] > sol[P[i]] + G[P[i]][j].second){
          v[G[P[i]][j].first]++;
         P[++k] = G[P[i]][j].first;
         sol[G[P[i]][j].first] = sol[P[i]] + G[P[i]][j].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));
    }
    Create();
    bfs();
    Afis();
    return 0;
}