#include <cstdio>
#include <queue>
#define nmax 50001
#include <vector>
#define INF 0x3f3f3f3f

using namespace std;

int M,N,cost[nmax],cnt[nmax];
bool in_q[nmax];
priority_queue <pair<int,int> > Q;
vector <pair<int,int> > G[nmax];

int main(){

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

  scanf("%d %d ",&N,&M);
  int x,y,z;

  while(M--){
    scanf("%d %d %d ",&x,&y,&z);
    G[x].push_back(make_pair(y,z));
  }

  for(x = 2;x <= N;x++)cost[x] = INF;

  bool ok = 0;
  Q.push(make_pair(0,1));
  in_q[1] = 1;
  while(!Q.empty() && ok == 0){
    x = Q.top().second;
    Q.pop();
    in_q[x] = 0;
    for(vector <pair<int,int> > :: iterator it = G[x].begin();it != G[x].end();++it){
      if(cost[it->first] > cost[x] + it->second){
	cost[it->first] = cost[x] + it->second;
	if(in_q[it->first] == 0){
	  if(cnt[it->first] == N){
	    ok = 1;
	    break;
	  }
	  in_q[it->first] = 1;
	  cnt[it->first]++;
	  Q.push(make_pair(-cost[it->first],it->first));
	}
      }
    }
  }

  if(ok)printf("Ciclu negativ!\n");
  else {
    for(x = 2;x <= N;x++)printf("%d ",cost[x]);
    printf("\n");
  }

  return 0;
  
}