#include <cstdio>

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

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

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

    start=1;

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

        scanf("%lld%lld",&x,&y);
        c[x][++c[x][0]].vfc=y;

        scanf("%lld",&c[x][++c[x][0]].cost);

    }
    /*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<=c[i][0];++i){

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

    tata[1]=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("%lld ",cmin[i]);
            //for(j=k-1;j>=1;--j){

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

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