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