#include<cstdio>
#include<vector>
#include<queue>
#define MAX 2000000000
using namespace std;
int n,m,x,jet,dist[50010],frecv[50010],fr[50010];
struct nod{
    int a,b;
};

vector<nod> v[50010];
queue<int> q;

void read(){
    nod val;
    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,&val.a,&val.b);
        v[x].push_back(val);
    }
}

void bellman(){
    q.push(1);
    frecv[1]=1;
    fr[1]=1;
    //inq[1]=true;
    nod y;
    while(!q.empty()){
        x=q.front();
        q.pop();
        //inq[x]=false;
        for(size_t i=0;i<v[x].size();i++){
            y=v[x][i];
            if(dist[x]+y.b < dist[y.a]){
                dist[y.a] = dist[x] + y.b;

                frecv[y.a]++;
                if(frecv[y.a] == n-1)
                    jet=1;
                if(fr[y.a] == 0){
                    fr[y.a]++;
                    q.push(y.a);
                }

            }//if
        }//for
        fr[x]=1;
    }

}

void rez(){
    dist[1]=0;
    for(int i=2;i<=n;i++)
        dist[i]=MAX;

    bellman();

    if(jet)
        printf("Ciclu negativ!\n");
    else
        for(int i=2;i<=n;i++)
            printf("%d ",dist[i]);
    printf("\n");
}

int main(){
    read();
    rez();
    return 0;
}