#include <cstdio>
#include <deque>

using namespace std;
FILE *f,*g;

int fr[50002],start[50002],t[3][250002],n,v[50002];
bool viz[50002];
deque <int> coada;

void bf(int nod)
{
    int poz,vecin;
    v[nod]=0;
    viz[nod]=1;
    coada.push_back(nod);
    while(!coada.empty())
    {
        nod=coada.front();
        coada.pop_front();
        viz[nod]=0;
        poz=start[nod];
        while(poz)
        {
            vecin=t[0][poz];
            if(v[nod]+t[2][poz]<v[vecin])
            {
                v[vecin]=v[nod]+t[2][poz];
                if(!viz[vecin])
                {
                    viz[vecin]=1,coada.push_back(vecin);
                    if(++fr[vecin]>n)
                    {
                        fprintf(g,"Ciclu negativ!\n");
                        fr[0]=1;
                        return;
                    }
                }
            } poz=t[1][poz];
        }
    }
}
int main()
{
    f=fopen("bellmanford.in","r");
    g=fopen("bellmanford.out","w");
    int m;
    int k=0,x,y;
    fscanf(f,"%d %d",&n,&m);
    for(int i=1;i<=m;++i)
    {
        fscanf(f,"%d %d %d",&x,&y,&t[2][++k]);
        t[0][k]=y;
        t[1][k]=start[x];
        start[x]=k;
    }
    for(int i=1;i<=n;++i)
        v[i]=1999999999;
    bf(1);
    if(!fr[0])
        for(int i=2;i<=n;++i)
            fprintf(g,"%d ",v[i]);
    fclose(f);
    fclose(g);
    return 0;
}