#include <fstream>
#define inf 2000000000
using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
struct nod
{
    int val,cost;
    nod *urm;
};
typedef nod *pnod;
struct coada
{
    int val;
    coada *urm;
};
typedef coada *pcoada;
pcoada prim,prec,umblu;
pnod v[50003];
pnod p;
int dist[50003];
void ad(int x,int y,int c)
{
    p=new nod;
    p->urm=v[x]->urm;
    p->val=y;
    p->cost=c;
    v[x]->urm=p;
}
int main()
{
    int n,m,i,x,y,c,ok;
    f>>n>>m;
    prim=new coada;
    prim->urm=0;
    for(i=1;i<=n;i++)
    {
        v[i]=new nod;
        v[i]->urm=0;
        prec=new coada;
        prec->urm=prim->urm;
        prec->val=i;
        prim->urm=prec;
        dist[i]=inf;
    }
    dist[1]=0;
    prim=prim->urm;
    for(i=1;i<=m;i++)
    {
        f>>x>>y>>c;
        ad(x,y,c);
    }
    for(i=1;i<n;i++)
    {
        umblu=prim;
        prec=prim;
        ok=0;
        while(ok==0 and prim)
        {
            p=v[prec->val]->urm;
            while(p)
            {
                if(dist[p->val]>dist[prec->val]+p->cost)
                {
                    dist[p->val]=dist[prec->val]+p->cost;
                    ok=1;
                }
                p=p->urm;
            }
            if(ok==0)
            {
                prim=prim->urm;
            }
            prec=prec->urm;
        }
        while(prec)
        {
            p=v[prec->val]->urm;
            ok=0;
            while(p)
            {
                if(dist[p->val]>dist[prec->val]+p->cost)
                {
                    dist[p->val]=dist[prec->val]+p->cost;
                    ok=1;
                }
                p=p->urm;
            }
            if(ok==0)
            {
                umblu->urm=prec->urm;
                prec=prec->urm;
            }
            else
            {
                umblu=prec;
                prec=prec->urm;
            }
        }
    }
    ok=0;
    while(prim)
    {
        p=v[prim->val]->urm;
        while(p)
        {
            if(dist[p->val]>dist[prec->val]+p->cost)
                ok=1;
            p=p->urm;
        }
        prim=prim->urm;
    }
    if(ok==1)
        g<<"Ciclu negativ!";
    else
        for(i=2;i<=n;i++)
            g<<dist[i]<<" ";
    return 0;
}