#include <stdio.h>
#include <bitset>
#include <deque>
using namespace std;
FILE *f,*g;

int start[50002],t[4][500002],drum[50002],n,m,fr[50002],ok;
bitset <50002> viz;
deque <int>q;

void bellmanford()
{
    int no,nod,dr;
    q.push_back(1);
    viz[1]=1;
    drum[1]=0;
    while(!q.empty())
    {
        nod=q.front();
        viz[nod]=0;///nu mai este in coada
        ++fr[nod];///daca un nod a fost introdus de mai mult de n ori inseamna ca exista un ciclu negativ
        if(fr[nod]>n)
        {
            ok=1;
            break;
        }
        q.pop_front();
        no=start[nod];
        while(no)
        {
            dr=t[3][no];
            if(drum[t[0][no]]>dr+drum[nod])///am gasit o distanta mai buna de la nodul nod la nodul t[0][no]
            {
                drum[t[0][no]]=dr+drum[nod];
                if(!viz[t[0][no]])///daca nu am mai introdus nodul t[0][no] in coada
                {
                    q.push_back(t[0][no]);
                    viz[t[0][no]]=1;
                }
            }
            no=t[1][no];
        }
    }
}

void write()
{
    int i;
    if(!ok)
        for(i=2;i<=n;++i)
            fprintf(g,"%d ",drum[i]);
    else
        fprintf(g,"Ciclu negativ!");
}

int main()
{
    int i,j,k=0,o;
    f=fopen("bellmanford.in","r");
    g=fopen("bellmanford.out","w");
    fscanf(f,"%d %d",&n,&m);
    for(o=1;o<=m;++o)
    {
        ++k;
        fscanf(f,"%d %d %d",&i,&j,&t[3][k]);
        t[0][k]=j,t[1][k]=start[i],start[i]=k;
    }
    for(i=1;i<=n;++i) drum[i]=2000000000;
    bellmanford();
    write();
    fclose(f);
    fclose(g);
    return 0;
}