#include <fstream>
#include <algorithm>
using namespace std;

ifstream cin("bellmanford.in");
ofstream cout("bellmanford.out");

typedef struct ls
{
    int info, drum;
    ls *next;
}*nod;

int c, y, u, i, j, x, n, m, sol[50005];
nod a[50005];
int viz[50005];

void ad(int x, nod &y, int c)
{
    nod p=new ls;
    p->info=x;
    p->drum=c;
    p->next=y;
    y=p;
}


int main()
{
    cin>>n>>m;
    for (i=1; i<=m; ++i)
    {
        cin>>x>>y>>c;
        ad(y, a[x], c);
    }


    for (i=2; i<=n; ++i) sol[i]=20000;
    u=0;
    for (j=1; j<=m; ++j)
    for(i=1; i<=n; ++i)
    {
        for (nod p=a[i]; p; p=p->next)
            if (sol[i]+p->drum < sol[p->info])
            {
                sol[p->info]=sol[i]+p->drum;
                ++viz[p->info];
                if (viz[p->info]==n) {u=1; break; }
            }



    }
    if (u) cout<<"Ciclu negativ!\n";
    else
    for (i=2; i<=n; ++i) cout<<sol[i]<<' ';


    return 0;
}