#include <iostream>
#include <fstream>
#define Nmax 50001
#define Cmax 250000001

using namespace std;

ifstream f("bellmanford.in");
ofstream g("bellmanford.out");

struct nodl{
    int info;
    int cost;
    nodl *urm;
};

int m,n;
nodl *G[Nmax];
int d[Nmax];

void add(int x,int y,int z)
{
    nodl *k=new nodl;
    k->info=y;
    k->cost=z;
    k->urm=G[x];
    G[x]=k;
}

void citire()
{
    f>>n>>m;
    int x,y,z;
    for(int i=1;i<=m;i++)
    {
        f>>x>>y>>z;
        add(x,y,z);
    }
}

void maxv()
{
    d[1]=0;
    for(int i=2;i<=n;i++)
        d[i]=Cmax;
}

struct ec{
    int info;
    ec *urm;
};

bool prezc[Nmax];
int nrapar[Nmax];

bool BF()
{
    int x;
    ec *in=new ec;
    in->urm=NULL;
    in->info=1;
    ec *sf;
    sf=in;
    nodl *parc;
    ec *ad;
    nrapar[1]++;
    while(in!=NULL)
    {
        x=in->info;
        prezc[x]=false;
        for(parc=G[x];parc!=NULL;parc=parc->urm)
            if(d[parc->info]>d[x]+parc->cost)
            {
                d[parc->info]=d[x]+parc->cost;
                if(!prezc[parc->info])
                {
                    nrapar[parc->info]++;
                    if(nrapar[parc->info]>n)
                        return false;
                    prezc[parc->info]=true;
                    ad=new ec;
                    ad->info=parc->info;
                    sf->urm=ad;
                    ad->urm=NULL;
                    sf=ad;
                }
            }
            ec *k=in;
            in=in->urm;
            delete k;
    }
    return true;
}
void afis()
{
    for(int i=2;i<=n;i++)
        g<<d[i]<< " ";
}

int main()
{
    citire();
    maxv();
    if(BF())
        afis();
    else
        g<<"Ciclu negativ!";
    return 0;
}