#include <bits/stdc++.h>
#define NMAX 50005
#define inf 1000000000
using namespace std;
ifstream in ("bellmanford.in");
ofstream out ("bellmanford.out");

int n,m,cost[NMAX];
tuple<int,int,int> muchii[NMAX];

void afs()
{
    int i;
    for(i=2;i<=n;i++)
        out<<cost[i]<<' ';
}

bool relax()
{
    bool ok=0;
    int i,x,y,c;
    for(i=1;i<=m;i++){
        x=get<0>(muchii[i]);
        y=get<1>(muchii[i]);
        c=get<2>(muchii[i]);
        if(cost[y]>cost[x]+c){
            ok=1;
            cost[y]=cost[x]+c;
        }
    }
    return ok;
}

void bell()
{
    bool ok;
    int p=1;
    do
    {
        ok=relax();
        p++;
    }while(ok and p<=n-1);
    ok=relax();
    if(ok)
        out<<"Ciclu negativ!";
    else
        afs();
}

int main()
{
    int i,x,y,c;
    in>>n>>m;
    for(i=1;i<=m;i++){
        in>>get<0>(muchii[i])>>get<1>(muchii[i])>>get<2>(muchii[i]);
    }
    for(i=1;i<=n;i++)
        cost[i]=inf;
    cost[1]=0;
    bell();
    return 0;
}