#include<fstream>
#define usi unsigned short int
#define si short int
#define inf 1000000000L
#define nmax 50010
using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
int d[nmax],m;
usi n;

struct nod{
    usi x;
    si cost;
    nod *urm;
};
nod *lista[nmax];

struct nod2{
    usi x;
    nod2 *urm;
};

inline void adaug2(nod2 *&pr,nod2 *&ul,usi a)
{
    nod2 *p;
    p=new nod2;
    p->x=a;
    p->urm=NULL;
    if(pr==NULL)
    {
        pr=p;
        ul=p;
    }
    else
    {
        ul->urm=p;
        ul=p;
    }
}
int main()
{
    int vf=1;
    f>>n>>m;
    for(int i=1;i<=m;i++)
    {
        usi a,b;
        si c;
        f>>a>>b>>c;
        nod *p;
        p=new nod;
        p->x=b;
        p->cost=c;
        p->urm=lista[a];
        lista[a]=p;
    }
    nod *r;
    nod2 *pr1,*pr2,*ul1,*ul2;
    usi t[nmax],k,i;
    char viz[nmax];
    for(i=1;i<=n;i++)
    {
        d[i]=inf;

    }
    d[vf]=0;
    t[vf]=0;
    pr1=NULL;
    for(nod *p=lista[vf];p!=NULL;p=p->urm)
    {
        d[p->x]=p->cost;
        adaug2(pr1,ul1,p->x);
        t[p->x]=vf;
    }
    for(k=1;k<n;k++)
    {
        if(pr1==NULL)
            break;
        pr2=NULL;
        for(i=1;i<=n;i++)
            viz[i]=0;
        while(pr1!=NULL)
        {
            for(r=lista[pr1->x];r!=NULL;r=r->urm)
            {
                if(d[r->x]>d[pr1->x]+r->cost)
                {
                    d[r->x]=d[pr1->x]+r->cost;
                    t[r->x]=pr1->x;
                    if(viz[r->x]==0)
                    {
                        adaug2(pr2,ul2,r->x);
                        viz[r->x]=1;
                    }
                }
            }
                nod2 *p;
                p=pr1;
                pr1=pr1->urm;
                delete p;
        }
        pr1=pr2;
        ul1=ul2;
    }
    if(pr1==NULL)
    {
        for(int i=1;i<=n;i++)
            if(i!=vf)
            {
                if(d[i]==inf)
                    g<<"0 ";
                else
                    g<<d[i]<<" ";
            }
    }
    else
        g<<"Ciclu negativ!";

    f.close();
    g.close();
    return 0;
}