#include <bits/stdc++.h>
using namespace std;
int N,M,A,B,c,d[50001],ciclu[50001];
queue <int> coada;
vector <int> G[50001],C[50001];
bool bellmanford(){
    coada.push(1);
    while(!coada.empty()){
        int x=coada.front();
        if(++ciclu[x]>N)return false;
        for(int i=0;i<G[x].size();++i)
            if(d[G[x][i]]>d[x]+C[x][i])
                d[G[x][i]]=d[x]+C[x][i],coada.push(G[x][i]);
        coada.pop();
    }
    return true;
}
int main(){
    freopen("bellmanford.in","r",stdin);
    freopen("bellmanford.out","w",stdout);
    scanf("%d%d",&N,&M);
    while(M--){
        scanf("%d%d%d",&A,&B,&c);
        G[A].push_back(B),C[A].push_back(c);
    }
    for(int i=2;i<=N;++i)d[i]=0x3f3f3f3f;
    bool ok=bellmanford();
    if(ok)for(int i=2;i<=N;++i)printf("%d ",d[i]);
    else printf("Ciclu negativ!");
    return 0;
}