#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,*sol[Nmax],k;
struct node
{
    int info,x;
    node *urm;
}*v[Nmax+5],*c,*d,*e,*f,*g;
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]=NULL;
    }
    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]=&d->info;e=d;}
    }
    for(int i=1;i<=n;i++)
    {
        a=0;
        c=v[1];
        while(c->urm)
        {
            k=0;
            g=c;
            c=c->urm;
            d=v[c->x];
            while(d->urm)
            {
                d=d->urm;
                if(sol[d->x]==NULL)
                    {
                        f=new node;
                        f->info=d->info+c->info;
                        f->x=d->x;
                        f->urm=0;
                        e->urm=f;
                        sol[f->x]=&f->info;
                        e=f;
                    }
                else if(*sol[d->x]>d->info+c->info)
                    {*sol[d->x]=d->info+c->info;a=1;k++;}
            }
            if(!k)
                g->urm=c->urm;
        }
    }
    if(a)
    {fout<<"Ciclu negativ!";return 0;}
    for(int i=2;i<n;i++)
        fout<<*sol[i]<<" ";
    fout<<*sol[n];
    return 0;
}