#include <iostream>
#include <fstream>
#define Nmax 50000
#define Nmax 250000
#define inf 1001
using namespace std;
ifstream fin ("bellmanford.in");
ofstream fout("bellmanford.out");
int n,m,a;
bool afara[Nmax];
struct node
{
    int info,x;
    node *urm;
}*v[Nmax+5],*c,*d,*e,*f;
struct pls
{
    int *val;
    bool afara;
}sol[Nmax];
int main()
{
    fin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        v[i]=new node;
        v[i]->info=i;
        v[i]->urm=0;
        sol[i].val=NULL;
        sol[i].afara=false;
    }
    int x1,y1,z1,a=1,b;
    while(fin>>x1>>y1>>z1)
    {
        c=v[x1];
        while(c->urm)
            c=c->urm;
        d=new node;
        d->info=z1;
        d->x=y1;
        d->urm=0;
        c->urm=d;
        if(x1==1)
            {sol[y1].val=&d->info;e=d;}
    }
    for(int i=1;i<=n;i++)
    {
        a=0;
        c=v[1];
        while(c->urm)
        {
            c=c->urm;
            if(sol[c->x].afara==false)
            {sol[c->x].afara=true;
            d=v[c->x];
            while(d->urm)
            {
                d=d->urm;
                if(sol[d->x].val!=NULL)
                cout<<c->x<<" "<<d->x<<" "<<*sol[d->x].val<<" "<<d->info+c->info<<"\n";
                if(sol[d->x].val==NULL)
                    {
                        f=new node;
                        f->info=d->info+c->info;
                        f->x=d->x;
                        f->urm=0;
                        e->urm=f;
                        sol[f->x].val=&f->info;
                        e=f;
                        sol[f->x].afara=false;
                    }
                else if(*sol[d->x].val>d->info+c->info)
                    {*sol[d->x].val=d->info+c->info;a=1;sol[d->x].afara=false;}
            }
        }
    }}
    if(a)
    {fout<<"Ciclu negativ!";return 0;}
    for(int i=2;i<n;i++)
        fout<<*sol[i].val<<" ";
    fout<<*sol[n].val;
    return 0;
}