#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <utility>
using namespace std;

#define MAXN 50010
#define INF 0x3f3f3f3f

int main(){

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

  int N, M, i, a, b, c, err, n;
  int in_queue[MAXN], use[MAXN], D[MAXN];
  queue<int> Q;
  vector< pair<int,int> > G[MAXN];
  vector< pair<int,int> >::iterator ii;  

  scanf("%d%d", &N, &M);

  for(i=0; i<M; i++){
    scanf("%d%d%d", &a, &b, &c);
    G[a].push_back(make_pair(b, c));
  }

  err=0;
  memset(use, 0, sizeof(use));
  memset(D, INF, sizeof(D));
  memset(in_queue, 0, sizeof(in_queue));

  D[1]=0; Q.push(1); in_queue[1]=1;
  while(!Q.empty() && !err){
    n=Q.front();
    Q.pop();
    in_queue[n]=0;
    
    for(ii=G[n].begin(); ii!=G[n].end(); ii++){
      if(D[n]+ii->second < D[ii->first]){
	D[ii->first]=D[n]+ii->second;
	if(!in_queue[ii->first]){
	  if(use[ii->first] >= N)
	    err=1;
	  else {
	    in_queue[ii->first]=1;
	    use[ii->first]++;
	    Q.push(ii->first);
	  }
	}
      }
    }
  }

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

}