#include <iostream>
#include <fstream>

using namespace std;

fstream f,g;

int n,m,i,j,k,l,er;

struct lst
{
    lst *urm;
    int cst,dst;
}*t;

struct lst2
{
    lst2 *urm,*prec;
    int id;
}*p,*vt;

struct nod
{
    char prez,verif;
    lst *p,*u;
    int cst;
    lst2 *orig;
}v[50001];

int trk(int i)
{
    v[i].prez=1;
    lst *t;
    for(t=v[i].p->urm;t!=NULL;t=t->urm)
        if(t->cst+v[i].cst<v[t->dst].cst)
        {
            if(v[t->dst].prez==1)
            {
                er=1;
                return 0;
            }
            v[t->dst].cst=t->cst+v[i].cst;
            if(v[t->dst].verif==0)
            {
                trk(t->dst);
                if(er==1)return 0;
            }
            else if(v[t->dst].orig->urm==NULL)
            {
                vt=v[t->dst].orig;
                vt->id=t->dst;
                p->prec->urm=vt;
                p->prec=vt;
                v[t->dst].orig=vt;
            }
        }
    v[i].prez=0;
    v[i].verif=1;
}

int main()
{
    f.open("bellmanford.in",ios_base::in);
    g.open("bellmanford.out",ios_base::out);
    f>>n>>m;
    for(i=1;i<=n;i++)
    {
        v[i].p=new lst;
        v[i].p->urm=NULL;
        v[i].u=v[i].p;
        v[i].cst=2e9;
    }
    v[1].cst=0;
    for(i=1;i<=m;i++)
    {
        f>>j>>k>>l;
        t=new lst;
        t->dst=k;
        t->cst=l;
        t->urm=NULL;
        v[j].u->urm=t;
        v[j].u=t;
    }
    p=new lst2;
    p->urm=p;
    p->prec=p;
    for(i=1;i<=n;i++)
    {
        v[i].orig=new lst2;
        v[i].orig->urm=NULL;
    }
    trk(1);
    if(er==1)
    {
        g<<"Ciclu negativ!";
        return 0;
    }
    while(p->urm!=p)
    {
        vt=p->urm;
        trk(vt->id);
        p->urm=vt->urm;
        vt->urm->prec=p;
        vt->urm==NULL;
    }
    for(i=2;i<=n;i++)g<<v[i].cst<<' ';
}