#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;
pnod p,v[50003];
void ad(int x,int y,int c)
{
    p=new nod;
    p->val=y;
    p->cost=c;
    p->urm=v[x]->urm;
    v[x]->urm=p;
}
int n,m,dist[50003];
struct coada
{
    int val;
    coada *prec,*urm;
};
typedef coada *pcoada;
pcoada act,prim,ultim,umblu;
void adaug(int x)
{
    act=new coada;
    act->val=x;
    act->urm=0;
    act->prec=ultim;
    ultim->urm=act;
    ultim=act;
}
void elimin()
{
    if(prim==ultim)
    {
        prim=ultim=umblu=0;
    }
    else
    {
        if(prim==umblu)
        {
            prim=prim->urm;
            prim->prec=0;
            umblu=prim;
        }
        else
            if(umblu==ultim)
            {
                ultim=ultim->prec;
                ultim->urm=0;
                umblu=0;
            }
            else
            {
                umblu->urm->prec=umblu->prec;
                umblu->prec->urm=umblu->urm;
                umblu=umblu->urm;
            }
    }
}
bool use[50003];
int main()
{
    int i,x,y,ok,c;
    f>>n>>m;
    for(i=1;i<=n;i++)
    {
        v[i]=new nod;
        v[i]->urm=0;
        dist[i]=inf;
    }
    dist[1]=0;
    for(i=1;i<=m;i++)
    {
        f>>x>>y>>c;
        ad(x,y,c);
    }
    prim=new coada;
    prim->urm=0;
    prim->prec=0;
    prim->val=1;
    ultim=prim;
    for(i=1;i<n;i++)
    {
        umblu=prim;
        while(umblu)
        {
            p=v[umblu->val]->urm;
            ok=0;
            while(p)
            {
                if(dist[p->val]>dist[umblu->val]+p->cost)
                {
                    ok=1;
                    dist[p->val]=dist[umblu->val]+p->cost;
                    if(use[p->val]^1)
                    {
                        use[p->val]=1;
                        adaug(p->val);
                    }
                }
                p=p->urm;
            }
            if(ok==0)
            {
                use[umblu->val]=0;
                elimin();
            }
            else
                umblu=umblu->urm;
        }
    }
    ok=0;
    while(prim)
    {
        p=v[prim->val]->urm;
        while(p)
        {
            if(dist[p->val]>dist[prim->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;
}