#include <iostream>
#include <cstdio>
#include <queue>
#include <vector>

using namespace std;

struct muchie{
  int a, b, cost;
};

int dist[50001];
bool inq[50001];
vector <pair <int,int>> v[50001];
queue <int> q;

int main() {
  FILE *fin, *fout;
  int n, m, i, j, x, y, c, st, nr;
  fin=fopen("bellmanford.in","r");
  fout=fopen("bellmanford.out","w");
  fscanf(fin, "%d%d",&n,&m);
  for(i=1;i<=m;i++) {
    fscanf(fin, "%d%d%d",&x,&y,&c);
    v[x].push_back({y,c});
  }
  for(i=1;i<=n;i++)
    dist[i]=1000000000;
  dist[1]=0;
  q.push(1);
  inq[1]=1;
  nr=1;
  while(q.size()!=0 && nr<=n*m) {
    x=q.front();
    nr++;
    for(i=0;i<v[x].size();i++) {
      if(dist[x]+v[x][i].second<dist[v[x][i].first]) {
        dist[v[x][i].first]=dist[x]+v[x][i].second;
        if(inq[v[x][i].first]==0) {
          q.push(v[x][i].first);
          inq[v[x][i].first]=1;
        }
      }
    }
    inq[x]=0;
    q.pop();
  }
  st=1;
  x=q.front();
  for(i=0;i<v[x].size();i++)
      if(dist[x]+v[x][i].second<dist[v[x][i].first]) {
      st=0;
      break;
  }
  if(st==0)
    fprintf(fout, "Ciclu negativ!");
  else
    for(i=2;i<=n;i++)
      fprintf(fout, "%d ",dist[i]);
  fclose( fin );
  fclose( fout );
  return 0;
}