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

#define MAX_N 50001
#define INF 200000000

struct Edge{
  int node,cost;
};

vector<Edge> graph[MAX_N];

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

void bf(int node){
  int qFront;
  long long i;
  for(i=1;i<=n;i++){
    marked[i]=false;
    dist[i]=INF;
  }

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

  while(!bfqueue.empty() && i<n*n){
    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(!marked[edge.node]){
          bfqueue.push(edge.node);
          marked[edge.node]=true;
        }
      }
    marked[qFront]=false;
    bfqueue.pop();
    i++;
  }
  if(i!=n*n)
    ok=1;
}

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;
}