#include <stdio.h>

const int nmax=50001;
const int mmax=250001;
const int INF=0x3F3F3F3F;
const int r=1;

struct element
{
    int nod,cost,next;
};

int head[nmax];
int d[nmax];
int coada[nmax*8];
bool ap[nmax];
int nrap[nmax];
element buff[mmax];

void push(int n1, int n2, int cost, int pos)
{
    buff[pos].nod=n2;
    buff[pos].cost=cost;
    buff[pos].next=head[n1];
    head[n1]=pos;
}

int main()
{
    FILE *f;
    int n,m,i,pos,a,b,c,prim,ultim,nc;
    bool ok;

    f=fopen("bellmanford.in","r");
    fscanf(f,"%d%d",&n,&m);
    for (i=1; i<=n; i++)
    {
        head[i]=-1;
        d[i]=INF;
    }
    pos=1;
    for (i=1; i<=m; i++)
    {
        fscanf(f,"%d%d%d",&a,&b,&c);
        push(a,b,c,pos);
        pos++;
    }
    fclose(f);

    ok=true;
    prim=ultim=1;
    coada[prim]=r;///pun radacina in coada
    d[r]=0;///si la fel este si tatal
    while (prim <= ultim && ok)///coada nevida si nu am gasit ciclu negativ
    {
        nc=coada[prim];
        nrap[nc]++;
        ap[nc]=false;///extrag primul nod din coada
        prim++;

        if (nrap[nc] > n)///se incearca actualizarea vecinilor unui nod de mai mult de n ori
            ok=false;///exista ciclu negativ
        else
        {
            i=head[nc];
            while (i != -1)///vizitez vecinii nodului curent
            {
                if (d[nc]+buff[i].cost < d[buff[i].nod])///daca distanta pana la vecini se poate imbunatati
                {
                    d[buff[i].nod]=d[nc]+buff[i].cost;///o imbunatatesc
                    if (!ap[buff[i].nod])///daca vecinul nu este in coada deja
                    {
                        ap[buff[i].nod]=true;///marchez ca este
                        ultim++;
                        coada[ultim]=buff[i].nod;///il pun in coada
                    }
                }
                i=buff[i].next;
            }
        }
    }

    f=fopen("bellmanford.out","w");
    if (!ok)
        fprintf(f,"Ciclu negativ!");
    else
        for (i=2; i<=n; i++)
            fprintf(f,"%d ",d[i]);
    fclose(f);
}