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