#include<cstdio>
#define maxn 50003
#include<queue>
#include<vector>
#define inf 9999999
using namespace std;
vector <int > C[maxn],G[maxn];
int n,m,x,y,c;
queue <int> Q;
vector <int > d,nr;
vector <bool> check;
int Bell(){
    nr.resize(n+2);
    d.resize(n+2,inf);
    check.resize(n+2);
    d[1]=0;
    nr[1]=1;
   // check[1]=true;

    Q.push(1);
    for(;!Q.empty();){
        int x=Q.front(); Q.pop();
           //--nr[x];
           //check[x]=false;
        for(int i=0;i<G[x].size();++i){

            int p=G[x][i];
            if(d[x]<inf)
            if(d[p]>C[x][i]+d[x]){
                d[p]=C[x][i]+d[x];
           // if(check[p]==false)
                if(nr[p]==n){
                    return 0;
                }
            else{
                //check[p]=true;
                Q.push(p);
                ++nr[p];
            }
        }
    }
    }
    return 1;
}
int main(){
    freopen("bellmanford.in","r",stdin);
    freopen("bellmanford.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i){
        scanf("%d%d%d", &x, &y, &c);
        C[x].push_back(c);
        G[x].push_back(y);
    }
    if(Bell())
        for(int i=2;i<=n;++i)
            printf("%d ",d[i]);
    else
        printf("Ciclu negativ!");
    return 0;
}