#include <cstdio>

using namespace std;
const int N=50005;
const int MOD=50000;
const int M=250005;
int p,n,m;
int lst[N],urm[M],vf[M],cost[M],sum[N],coada[N],incoada[N],nr[N];
void ad(int x,int y,int c)
{
    p++;
    vf[p]=y;
    urm[p]=lst[x];
    lst[x]=p;
    cost[p]=c;
}
bool bfs()
{
    int st=0,dr=1,poz,x,y;
    while(st!=dr)
    {
        x=coada[st];
        incoada[x]=0;
        st=(st+1)%MOD;
        poz=lst[x];
        while(poz!=0)
        {
            y=vf[poz];
            if(sum[x]+cost[poz]<sum[y])
            {
                sum[y]=sum[x]+cost[poz];
                if(incoada[y]==0)
                {
                    incoada[y]=1;
                    coada[dr]=y;
                    dr=(dr+1)%MOD;
                    nr[y]++;
                    if (nr[y] == n)
                        return false;
                }
            }
            poz=urm[poz];
        }
    }
    return true;
}
int main()
{
    FILE *in,*out;
    in=fopen("bellmanford.in","r");
    out=fopen("bellmanford.out","w");
    int x,y,c,i;
    fscanf(in,"%d%d",&n,&m);
    for(i=1; i<=m; i++)
    {
        fscanf(in,"%d%d%d",&x,&y,&c);
        ad(x,y,c);
    }
    coada[0]=1;
    incoada[1]=1;
    for(i=1;i<=n;i++)
        sum[i]=99999999;
    sum[1]=0;
    if(bfs())
        for(i=2; i<=n; i++)
            fprintf(out,"%d ",sum[i]);
    else
        fprintf(out,"Ciclu negativ!");
    return 0;
}