#include <stdio.h>
#include <queue>
#include <cstdlib>
#define INF 1073741821

using namespace std;

int inc[50002],d[50002],viz[50002];
struct muchie
{
    int x,y,c;
}v[250001];

int cmp(const void *i, const void *j)
{
    return ((muchie*)i)->x - ((muchie*)j)->x;
}

int main()
{
    freopen("bellmanford.in","r",stdin);
    freopen("bellmanford.out","w",stdout);
    int n,m,i,j,a,k,u,nu,ok,nasol=0;
    queue<int> c[2];
    scanf("%d%d",&n,&m);
    for(i=0;i<m;i++)
    {
        scanf("%d%d%d",&(v[i].x),&(v[i].y),&(v[i].c));
    }
    qsort(v,m,sizeof(muchie),cmp);

    for(i=0;i<=n;i++) {inc[i]=-1;d[i]=INF;}
    j=v[0].x;inc[j]=0;
    for(i=1;i<m;i++)
        if(v[i].x!=v[i-1].x)
            inc[v[i].x]=i;

    d[1]=0;viz[1]=1;
    c[0].push(1);
    u=1;nu=0;
    for(k=1;k<n;k++)
    {
        u=nu;nu=!u;
        while(!c[u].empty())
        {
            a=c[u].front();
            c[u].pop();
            ok=0;
            for(i=inc[a];v[i].x==a;i++)
            {
                if(d[v[i].y]>d[a]+v[i].c)
                {
                    d[v[i].y]=d[a]+v[i].c;ok=1;
                    if(viz[v[i].y]==0) {c[u].push(v[i].y);viz[v[i].y]=1;}
                }
            }
            if(ok) c[nu].push(a);
            else viz[a]=0;
        }
    }

        u=nu;
        while(!c[u].empty()&&!nasol)
        {
            a=c[u].front();
            c[u].pop();
            for(i=inc[a];v[i].x==a;i++)
            {
                if(d[v[i].y]>d[a]+v[i].c) {d[v[i].y]=d[a]+v[i].c;nasol=1;c[u].push(v[i].y);break;}
            }
        }

    if(nasol) printf("Ciclu negativ!");
    else {for(k=2;k<=n;k++)
        printf("%d ",d[k]);
    }
    return 0;
}