#include <iostream>
#include <fstream>
using namespace std;
int dmin[50003];
struct la
{
    int ind,dist;
    la *urm;
} *p;
struct vla
{
    la *urm;
} v[50003];
int n,m,i,x,y,d,i1,b;
int main(void)
{
    FILE * f;
    f=fopen("bellmanford.in","r");
    ofstream g("bellmanford.out");
    fscanf(f,"%d%d",&n,&m);
    for (i=1;i<=n;i++)
    {
        p=new(la);
        v[i].urm=p;
        p->urm=NULL;
        p->ind=0;
        dmin[i]=999999999;
    }
    for (i=1;i<=m;i++)
    {
        fscanf(f,"%d%d%d",&x,&y,&d);
        p=new(la);
        p->urm=v[x].urm;
        v[x].urm=p;
        p->ind=y;
        p->dist=d;
        if (x==1)
            dmin[y]=d;
    }
    for (i=1;i<=n-1;i++)
        for (i1=1;i1<=n;i1++)
            {
                p=v[i1].urm;
                while (p->urm!=NULL)
                {
                    if (dmin[i1]+p->dist<dmin[p->ind])
                        dmin[p->ind]=dmin[i1]+p->dist;
                    p=p->urm;
                }
            }
    b=0;
    for (i=1;i<=n;i++)
    {
        p=v[i].urm;
        while (p->urm!=NULL)
        {
            if (dmin[i]+p->dist<dmin[p->ind])
                    b=1;
            p=p->urm;
        }
    }
    if (b==1)
        g<<"Ciclu negativ!";
    else
        for (i=2;i<=n;i++)
            g<<dmin[i]<<' ';
    g<<'\n';
    g.close();
    return 0;


}