#include <iostream>
#include <fstream>

using namespace std;

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

int n,m,t[3][250001],start[50001],cost[50001],coada[1000000],viz[50001],fr[50001],ok=1;

void citire()
{
    int i,k=0,x,y,costi;
    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>x>>y>>costi;
        k++;
        t[2][k]=costi;
        t[0][k]=y;
        t[1][k]=start[x];
        start[x]=k;
    }
}

void costuri()
{
    cost[1]=0;
    for(int i=2;i<=n;i++)
        cost[i]=99999;
}
void belman()
{
    int pi,ps,i,x,vecin;
    pi=ps=1;
    viz[1]=1;
    coada[1]=1;
   while(ps<=pi)
    {
        x=coada[ps];
        fr[x]++;
        if(fr[x]>=n)
        {
            ok=0;
            break;
        }
        vecin=start[x];
        while(vecin)
        {
            if(cost[x]+t[2][vecin]<cost[t[0][vecin]])
            {
                cost[t[0][vecin]]=cost[x]+t[2][vecin];
                if(viz[t[0][vecin]]==0)
                {
                    viz[t[0][vecin]]=1;
                    coada[++pi]=t[0][vecin];
                }
            }
            vecin=t[1][vecin];
        }
        viz[x]=0;
        ps++;
    }

}

int main()
{
    citire();
    costuri();
    belman();
    if(ok==1)
    {
        for(int i=2;i<=n;i++)
            g<<cost[i]<<" ";
    }
    else
        g<<"Ciclu negativ!";
    return 0;
}