#include <iostream>
#include <fstream>
#define nmax 50000
#define inf 1001
using namespace std;
ifstream fin ("bellmanford.in");
ofstream fout("bellmanford.out");
int n,m,dist[nmax+5],nr[nmax+5];
struct node
{
    int info,x;
    node *urm;
}*v[nmax+5],*d,*e[nmax+5],*g;
struct que
{
    int info;
    que *urm,*ante;
}*a,*b,*c,*prez;
void pop()
{
    b=b->ante;
    b->urm=0;
}
void push(int x)
{
    if(a->urm!=0)
    {
    c=new que;
    c->info=x;
    c->urm=0;
    c->ante=b;
    b->urm=c;
    b=c;
    }
    else
    {
    c=new que;
    c->info=x;
    c->urm=0;
    c->ante=a;
    a->urm=c;
    b=c;
    }
}
int main()
{
    int ok=1,cost;
    fin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        v[i]=new node;
        v[i]->info=i;
        v[i]->urm=0;
        e[i]=v[i];
    }
    int x1,y1,z1;
    for(int i=2;i<=n;i++)
        dist[i]=inf;
    while(fin>>x1>>y1>>z1)
    {
        d=new node;
        d->info=y1;
        d->x=z1;
        d->urm=0;
        e[x1]->urm=d;
        e[x1]=d;
        if(x1==1)
            dist[e[x1]->info]=e[x1]->x;
    }
    a=new que;
    a->urm=a->ante=0;
    a->info=0;
    push(1);
    while(a->urm!=0 && ok)
    {
        prez=b;
        pop();
        d=v[prez->info];
        while(d->urm)
        {
            d=d->urm;
            cost=d->x;
            g=v[d->info];
            while(g->urm)
            {
               g=g->urm;
            if(dist[g->info]>dist[d->info]+cost)
                {
                    dist[d->info]=dist[prez->info]+cost;
                    nr[d->info]++;
                    if(nr[g->info]==n)
                        {ok=0;break;}
                    push(g->info);
                }
        }
    }
    }
    if(!ok)
        fout<<"Ciclu negativ!\n";
    else
    {for(int i=2;i<=n;i++)
        fout<<dist[i]<<" ";
        fout<<"\n";}
    delete a;
    delete b;
    delete c;
    delete d;
    delete prez;
    return 0;
}