#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define M 250010
#define N 50100
#define VALMAX 25010000

using namespace std;

struct muc{
    int x,y,cost;
};
struct muc lis[M];
int ifin,dist[N];

void add_vertex(int x,int y,int val);

int main(){
    int n,m,spy;
    int i,j,x,y,cost;

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

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

    for(i=0;i<m;i++){
        scanf("%d %d %d",&x,&y,&cost);
        add_vertex(x,y,cost);
    }

    memset(dist,VALMAX,(n+2)*sizeof(int));
    spy=1;
    dist[1]=0;
    for(i=0;i<n-1 && spy;i++){
        spy=0;

        for(j=0;j<m;j++){
            x=lis[j].x;
            y=lis[j].y;
            cost=lis[j].cost;

            if(dist[x]+cost<dist[y]){
                spy=1;
                dist[y]=dist[x]+cost;
            }
        }

    }

    for(j=0;j<m;j++){
        x=lis[j].x;
        y=lis[j].y;
        cost=lis[j].cost;

        if(dist[x]+cost<dist[y]){
            printf("Ciclu negativ!");
            return 0;
        }
    }
    for(i=2;i<=n;i++){
        printf("%d ",dist[i]);
    }

    return 0;
}

void add_vertex(int x,int y,int val){
    lis[ifin].x=x;
    lis[ifin].y=y;
    lis[ifin].cost=val;
    ifin++;
}