#include<cstdio>

using namespace std;

bool inq[50001];
int nr,lst[50001],urm[2500001],vf[2500001],d[50001],q[1000001],n,m,s;
int cost[250001];
const int INF=1000000000;
int nrq[50001];

void adauga (int x,int y,int c)
{
    ++nr;
    vf[nr]=y;
    cost[nr] = c;
    urm[nr]=lst[x];
    lst[x]=nr;
}

bool bellmanford(int x0){

    int i,p=0,u=-1,poz,y,c;
    for(i=1;i<=n;i++){
        d[i]=INF;
    }
    d[x0]=0;
    q[++u]=x0;
    nrq[x0]++;
    inq[x0] = true;
    while(p<=u){
        x0=q[p++];
        poz=lst[x0];
        inq[x0] = false;
        while(poz!=0){
            y=vf[poz];
            c=cost[poz];
            if(d[x0]+c<d[y]){
                d[y]=d[x0]+c;
                if (!inq[y])
                {
                    inq[y] = true;
                    q[++u]=y;
                    nrq[y]++;
                    if(nrq[y]==n)
                        return false;
                }
            }
            poz = urm[poz];
        }
    }
    return true;
}

int main(){

    freopen("bellmanford.in","r",stdin);
    freopen("bellmanford.out","w",stdout);

    int i, x, y, c;

    scanf("%d%d",&n,&m);

    for(i=1;i<=m;i++){

        scanf("%d%d%d",&x,&y, &c);
        adauga(x,y,c);

    }
    if (!bellmanford(1))
        printf("Ciclu negativ!\n");
    else
        for (i = 2;  i <= n; i++)
            printf("%d ", d[i]);
    return 0;
}