#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]=999999;
}
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 ps=1,pi=1,x,vecin;
    viz[1]=1;
    coada[pi]=1;
    cost[1]=0;
    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();
    cost[1]=0;
    costuri();
    belman();
    if(ok==1)
    {
        for(int i=2;i<=n;i++)
            g<<cost[i]<<" ";
    }
    else
        g<<"Ciclu negativ!";
    return 0;
}