#include <stdio.h>
#include <string.h>

char ax[8192];
int pz;
const int oo = 1<<30;

inline void cit(int &x)
{
    x=0;
    int semn = 1;
    while(ax[pz]< '0' || ax[pz] > '9')
        if(++pz==8192)fread(ax,1,8192,stdin),pz=0;
    if(ax[pz-1] == '-')
        semn = -1;
    while(ax[pz]>='0' && ax[pz]<='9')
    {
        x=x*10+ax[pz]-'0';
        if(++pz==8192)fread(ax,1,8192,stdin),pz=0;
    }
    x*=semn;
}

struct nod { int x, y, c;};

nod a[2501];
int d[501];
int n, m;

void read()
{
    freopen("bellmanford.in","r",stdin);
    cit(n);cit(m);
    for(int i=1;i<=m;++i) cit(a[i].x), cit(a[i].y), cit(a[i].c);

}

void bell()
{
    int i;
    int p,q,c;
    bool mf = true;
    for(i=1; i<=n; i++)
        d[i] = oo;
    d[1]=0;
    int counter  = 0;

    while(mf && counter < n)
    {
        mf = false;
        for(i=1;i<=m;++i)
        {
            p=a[i].x, q=a[i].y, c=a[i].c;
            if(d[p] + c < d[q])
                d[q]=d[p]+c, mf = true;
        }
        counter++;
        /*for(i=1; i<=n; i++)
            printf("%d ", d[i]);
        printf("\n");*/
    }
    if(counter >= n)
        printf("Ciclu negativ!\n");
    else

    for(i=2;i<=n;++i)
        if(d[i]==oo) printf("0 ");
                else printf("%d ", d[i]);


}

int main()
{
    freopen("bellmanford.out","w",stdout);
    read();
    bell();
    return 0;
}