#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[N],vf[M],urm[M],q[2*M],cost[M],contor[N],ca;
long long d[N];
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 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;
                        return;
                    }
                }
            }
            poz=urm[poz];
        }
    }

}
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);
    }
    init();

        bell (1);
        if (negativ)
        {
            fprintf (out,"Ciclu negativ!");

        }


    if (!negativ)
    afisare();
}
int main()
{
    citire ();

    return 0;
}