#include <cstdio>

using namespace std;
FILE *in=fopen ("bellmanford.in","r");
FILE *out=fopen ("bellmanford.out","w");
const int M=250001;
int n,m,lst[M],vf[M],urm[M],d[M],q[M],cost[M],contor[M],ca;
bool inq[M],negativ,denevizitat[M];
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;
}
int 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 && !negativ)
    {
        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;
                        break;
                    }
                }
            }
            else denevizitat[x]=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--)
    {
        if (!denevizitat[i])
        {
            bell (i);
            if (negativ)
            {
                fprintf (out,"Ciclu negativ!");
                break;
            }
                init();
        }
    }
    if (!negativ)
    {
        init();
        bell(1);
        afisare();
    }
}
int main()
{
    citire ();
    return 0;
}