#include <stdio.h>
#include <vector>
#include <queue>

using namespace std;

#define NMAX 50005
#define INF 1e9

struct edge{
  int to;
  int cost;
};

vector <edge> g[NMAX+1];
queue <int> q;
int dist[NMAX+1],counter[NMAX+1],n;

int bellmanford(int nod){
  int first,i;
  counter[nod]++;
  q.push(nod);
  dist[1]=0;
  for(i=2;i<=n;i++){
    dist[i]=INF;
  }
  while(!q.empty()){
    first=q.front();
    for(auto next : g[first]){
      if(dist[first]+next.cost<dist[next.to]){
        counter[next.to]++;
        if(counter[next.to]==n){
          return 0;
        }
        dist[next.to]=dist[first]+next.cost;
        q.push(next.to);
      }
    }
    q.pop();
  }
  return 1;
}

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

  int m,x,y,c,i;
  fscanf(fin,"%d%d",&n,&m);
  for(i=1;i<=m;i++){
    fscanf(fin,"%d%d%d",&x,&y,&c);
    g[x].push_back({y,c});
  }
  if(bellmanford(1)==0){
    fprintf(fout,"Ciclu negativ!");
  }
  else{
    for(i=2;i<=n;i++){
      fprintf(fout,"%d ",dist[i]);
    }
  }
  fclose(fin);
  fclose(fout);
  return 0;
}