#include <cstdio>
#include <list>
#define nmax 50001
#define inf 0x3f3f3f3f
#define mmax 250001

using namespace std;

int N,M;
struct per
{
  int u,v,c;
} V[mmax];
int cost[nmax];

void verif(){

  for(int i = 1;i <= M;i++)
    if(cost[V[i].u] + V[i].c < cost[V[i].v]){
      printf("Ciclu negativ!\n");
      return;
    }

  for(int i = 2;i <= N;i++)printf("%d ",cost[i]);
  printf("\n");
  
}

int main(){

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

  scanf("%d %d ",&N,&M);
  int x,y,z,w;
  for(w = 1;w <= M;w++){
    scanf("%d %d %d ",&x,&y,&z);
    V[w].u = x;
    V[w].v = y;
    V[w].c = z;
  }

  for(x = 2;x <= N;x++){
    cost[x] = inf;
    
  }

  cost[1] = 0;

  for(x = 1;x < N;x++){

    for(w = 1;w <= M;w++){
      if(cost[V[w].u] + V[w].c < cost[V[w].v]){
	cost[V[w].v] = cost[V[w].u] + V[w].c;
      }
    }
    
  }

  verif();
  
  return 0;
  
}