#include <cstdio>

using namespace std;
const int INF=2000000000;
int n,m,start,i,j,k,x,y,check,c[5000][5000],cmin[50000],tata[50000],v[50000];

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

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

    start=1;

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

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

    }
    for(i=1;i<=n;++i){
        for(j=1;j<=n;++j){

            if(c[i][j]==0 && i!=j){

                c[i][j]=INF;

            }

        }
    }

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

        cmin[i]=c[start][i];
        tata[i]=start;
    }

    tata[start]=0;
    for(i=1;i<=n;++i){
        check=0;
        for(j=1;j<=n;++j){

            for(k=1;k<=n;++k){

                if(c[j][k]!=INF && j!=k){

                    if(cmin[k]>cmin[j]+c[j][k]){

                        cmin[k]=cmin[j]+c[j][k];
                        tata[k]=j;
                        check=1;

                    }

                }

            }

        }

    }

    if(check==1){printf("Ciclu negativ!");}

    else {
        for(i=2;i<=n;++i){
            if(i!=start){
            //k=1;
            //v[k]=i;
            //while(v[k]!=0){

                //v[++k]=tata[v[k-1]];

            //}
            printf("%d ",cmin[i]);
            //for(j=k-1;j>=1;--j){

                //printf("%d ",v[j]);

            }
            //printf("\n");
            //}
        }
    }
    return 0;
}