#include <stdio.h>
#include <vector>
#include <queue>
using namespace std;

#define MAX_N 100000
#define INF 100000000

struct Edge{
  int node,cost;
};

vector<Edge> graph[MAX_N];

queue<int> bfqueue;
int dist[MAX_N],marked[MAX_N];
int n,ok;

void bf(int node){
  int i,qFront;

  for(i=1;i<=n;++i){
    marked[i]=false;
    dist[i]=INF;
  }

  dist[node]=0;
  bfqueue.push(node);
  marked[node]=true;

  while(!bfqueue.empty()){
    qFront=bfqueue.front();

    for(const Edge& edge : graph[qFront])
      if(dist[edge.node]>dist[qFront]+edge.cost){
        dist[edge.node]=dist[qFront]+edge.cost;
        if(dist[edge.node]<0)
          ok=1;
        if(!marked[edge.node]){
          bfqueue.push(edge.node);
          marked[edge.node]=true;
        }
      }

    marked[qFront]=false;
    bfqueue.pop();
  }
}

int main(){
  FILE *fin,*fout;
  fin=fopen("bellmanford.in","r");
  fout=fopen("bellmanford.out","w");

  int m,i,a,b,c;
  fscanf(fin,"%d%d",&n,&m);
  for(i=0;i<m;i++){
    fscanf(fin,"%d%d%d",&a,&b,&c);
    graph[a].push_back({b,c});
  }

  ok=0;
  bf(1);

  if(ok==1)
    for(i=2;i<=n;i++)
      fprintf(fout,"%d ",dist[i]);
  else
    fprintf(fout,"Ciclu negativ!");
  fclose(fin);
  fclose(fout);
  return 0;
}