#include <stdio.h>
#include <bitset>
#include <deque>
using namespace std;
FILE *f,*g;
bitset <50002> viz;
deque <int>q;
int start[50002],a[4][500002],drum[50002],fr[50002];
int n,m,ok;

void bellmanford()
{
    int no,nod,dr;
    q.push_back(1);
    viz[1]=1;
    drum[1]=0;
    while(!q.empty())
    {
        nod=q.front();
        q.pop_front();
        viz[nod]=0;
        ++fr[nod];
        if(fr[nod]>n)
        {
            ok=1;
            break;
        }
        no=start[nod];
        while(no)
        {
            dr=a[3][no];
            if(drum[a[0][no]]>dr+drum[nod])
            {
                drum[a[0][no]]=dr+drum[nod];
                if(!viz[a[0][no]])
                {
                    q.push_back(a[0][no]);
                    viz[a[0][no]]=1;
                }
            }
            no=a[1][no];
        }
    }
}

void afisare()
{
    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,l;
    f=fopen("bellmanford.in","r");
    g=fopen("bellmanford.out","w");
    fscanf(f,"%d %d",&n,&m);
    for(l=1;l<=m;++l)
    {
        ++k;
        fscanf(f,"%d %d %d",&i,&j,&a[3][k]);
        a[0][k]=j;
        a[1][k]=start[i];
        start[i]=k;
    }
    for(i=1;i<=n;++i) drum[i]=2000000000;
    bellmanford();
    afisare();
    fclose(f);
    fclose(g);
    return 0;
}