#include <fstream>
#include <stdlib.h>
#define NMAX 1004

using namespace std;

ifstream cin("bellmanford.in");
ofstream cout("bellmanford.out");

struct nod{int nr,c;nod*urm;};
typedef nod*Lista;
Lista lis[NMAX];

struct coada{int nr;coada*urm;};
typedef coada*Coada;
Coada p=NULL,u=NULL;

int n,d[NMAX],start=1,nr[NMAX],tata[NMAX],m;

void read();
void solve();
void inserare_lista(Lista&,int,int);
void inserare_coada(int);
void write();

int main()
{
    read();
    solve();
    write();
    cin.close();cout.close();
    return 0;
}

void read()
{
    int x,y,c,i;
    cin>>n>>m;
    for (i=1;i<=n;i++)
        {lis[i]=NULL;d[i]=1000000000;}
    for (i=1;i<=m;i++)
    {
        cin>>x>>y>>c;
        inserare_lista(lis[x],y,c);
    }
    d[start]=0;
}

void inserare_lista(Lista&prim,int nr,int ct)
{
    Lista aux;
    aux=new nod;
    aux->nr=nr;
    aux->c=ct;
    aux->urm=prim;
    prim=aux;
}

void inserare_coada(int nr)
{
    Coada aux;
    aux=new coada;
    aux->nr=nr;
    aux->urm=NULL;
    if (u==NULL)
        p=u=aux;
    else
    {
        u->urm=aux;
        u=aux;
    }
}

void solve()
{
    int x;Lista aux;Coada aaux;
    inserare_coada(start);
    nr[start]=1;
    while (p!=NULL)
    {
        x=p->nr;
        aux=lis[x];
        while (aux!=NULL)
        {
            if (d[aux->nr]>d[x]+aux->c)
            {
                d[aux->nr]=d[x]+aux->c;
                tata[aux->nr]=x;
                inserare_coada(aux->nr);
                nr[aux->nr]++;
                if (nr[aux->nr]==n)
                {
                    cout<<"Ciclu negativ!\n";
                    cin.close();cout.close();
                    exit(0);
                }
            }
            aux=aux->urm;
        }
        aaux=p;
        p=p->urm;
        delete aaux;
    }
}

void write()
{
    int i;
    for (i=2;i<=n;i++)
        cout<<d[i]<<' ';
    cout<<'\n';
}