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

char ax[290000];
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==290000)fread(ax,1,290000,stdin),pz=0;
    if(ax[pz-1] == '-')
        semn = -1;
    while(ax[pz]>='0' && ax[pz]<='9')
    {
        x=x*10+ax[pz]-'0';
        if(++pz==290000)fread(ax,1,290000,stdin),pz=0;
    }
    x*=semn;
}

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

nod a[250001];
int d[50001];
int n, m;

void read()
{
    freopen("dijkstra.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);

}

bool viz[50001]={false};

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)
    {
        mf = false;
        for(i=1;i<=m;++i)
        {
            p=a[i].x, q=a[i].y, c=a[i].c;

            //if(!viz[p] || d[q] == oo){
                if(d[p] + c < d[q]){
                    d[q]=d[p]+c;
                    mf = true;
                    viz[q] = false;
                }
                //else
                    //viz[q] = true;
            //}
        }
        counter++;
        /*for(i=1; i<=n; i++)
            printf("%d ", d[i]);
        printf("\n");*/
    }
    if(mf)
        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("dijkstra.out","w",stdout);
    read();
    bell();
    return 0;
}