#include <cstdio>

using namespace std;
FILE *in=fopen ("bellmanford.in","r");
FILE *out=fopen ("bellmanford.out","w");
const int M=250001,N=50001;
int n,m,lst[M],vf[M],urm[M],d[N],q[N],cost[N],contor[N],ca;
bool inq[N],negativ;
void adauga (int x,int y,int z)
{
    vf[++m]=y;
    cost[m]=z;
    urm[m]=lst[x];
    lst[x]=m;
}
void init ()
{
    for (int i=1; i<=n; i++)
        d[i]=999999999;
}
void resetare ()
{
    for (int i=1;i<=n;i++)
    contor[i]=0;
}
bool bell (int x)
{
    int p=1,u=0,poz,y;
    d[x]=0;
    inq[x]=true;
    contor[x]+=1;
    q[++u] = x;
    while (p<=u)
    {
        x=q[p++];inq[x]=false;
        poz=lst[x];
        while (poz!=0)
        {
            y=vf[poz];
            ca=cost[poz];
            if ((d[x]+ca)<d[y])
            {
                d[y]=d[x]+ca;
                if (!inq[y])
                {
                    q[++u]=y;
                    inq[y]=true;
                    contor[y]++;
                    if (contor[y]==n) negativ=true;
                }
            }
            poz=urm[poz];
        }
    }
    resetare ();
}
void afisare ()
{
    for (int i=2;i<=n;i++)
    fprintf (out,"%d ",d[i]);
}
void citire ()
{
    int a;
    fscanf (in,"%d%d",&n,&a);
    for (int i=0;i<a;i++)
    {
        int x,y,c;
        fscanf (in,"%d%d%d",&x,&y,&c);
        adauga (x,y,c);
    }
    for (int i=n;i>=1;i--)
    {
        bell (i);
        if (negativ)
        {
            fprintf (out,"Ciclu negativ!");
            break;
        }
        if (i!=1)
        init();
    }
    if (!negativ)
    afisare();
}
int main()
{
    citire ();
    return 0;
}