#include <iostream>
#include <fstream>
#include <queue>
#define INF 9999
using namespace std;
ifstream in("bellmanford.in");
ofstream out("bellmanford.out");

int n,m;

/*struct muchie{
    int x,y,cost;
}v[250005]; //vector muchii*/

int d[50005]; //vector distante minime st->i
queue <int> c; //coada noduri vizitate
int viz[250005];   //vector noduri vizitate (care se afla in coada)

struct vecin{
    //inform utila
    int nod, cost;
    //inform de legatura
    struct vecin *urm;
}*L[50005],*act;

bool parcurge(int rad)
{
    for(int i=1;i<=n;++i)
        viz[i]=0;

    bool act=false;
    c.push(rad);
    viz[rad]=1;

    while(!c.empty())
    {
        int nod=c.front();
        c.pop();
        for(struct vecin *p=L[nod];p!=NULL;p=p->urm)
        {
            int vecin=p->nod;
            int cost=p->cost;
            if(viz[vecin]==0 && d[vecin]>d[nod]+cost)
            {
                d[vecin]=d[nod]+cost;
                c.push(vecin);
                act=true;
            }
        }
    }
    return act;
}

int main()
{
//citiri
    int x,y,cost;
    in>>n>>m;
    for(int i=1;i<=m;++i)
    {
        in>>x>>y>>cost;
        //adauga vecinul y la lista x
        act=new vecin;
        act->nod=y;
        act->cost=cost;
        act->urm=L[x];
        L[x]=act;
    }
//bellman ford din nodul nr. 1
    //initializeaza distantele cu +INF
    for(int i=1;i<=n;++i)
        d[i]=INF;
    d[1]=0;
    //treci prin toate muchiile de n-1 ori, actualizand distantele minime
    for(int i=1;i<=n-1;++i)
        parcurge(1);

    //daca la a n-a parcurgere, avem o actualizare, atunci exista ciclu de cost negativ
    if(parcurge(1)==1)
        out<<"Ciclu negativ!\n";
    else
    {
        for(int i=2;i<=n;++i)
            out<<d[i]<<" ";
    }
    return 0;
}