#include <iostream>
#include <fstream>

using namespace std;

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

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

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

    }
}
void costuri()
{
    for(int i=2;i<=n;i++)
        cost[i]=99999;
}
void modif_cost(int prim_ele,int ind_vecin,int &pi)
{
    if(cost[prim_ele]+t[2][ind_vecin]<cost[t[0][ind_vecin]])
    {
        cost[t[0][ind_vecin]]=cost[prim_ele]+ t[2][ind_vecin];
        if(viz[t[0][ind_vecin]]==0)
        {
            pi++;
            coada[pi]=t[0][ind_vecin];
            viz[t[0][ind_vecin]]=1;
        }

    }
}
void belman()
{
    int pi,ps,i,x,cop;
    ps=pi=1;
    viz[pi]=1;
    coada[pi]=1;
    while(ps<=pi)
    {
        x=start[coada[ps]];
        cop=coada[ps];
        viz[cop]=0;
        fr[cop]++;
        if (fr[cop]>=n)
        {
            ok=0;
            break;
        }
        while(x!=0)
        {
            modif_cost(cop,x,pi);
            x=t[1][x];
        }
        ps++;
    }
}
int main()
{
    citire();
    cost[1]=0;
    costuri();
    belman();
    if(ok==1)
    {
        for(int i=2;i<=n;i++)
            g<<cost[i]<<" ";
    }
    else
        g<<"Ciclu negativ!";
    return 0;
}