#include <fstream>
#include <vector>
#include <queue>
#define INF 1000000000
using namespace std;

ifstream cin("bellmanford.in");
ofstream cout("bellmanford.out");

struct arc{
  int varf;
  int cost;
};

vector <arc> v[250001];
queue <int> q;

int d[50001], inqueue[50001], nr[50001];

int main(){
  int n, m, i, x, y, c;
  cin >> n >> m;
  for(i = 1; i <= m; ++i){
    cin >> x >> y >> c;
    v[x].push_back({y, c});
  }
  for(i = 1; i <= n; ++i)
    d[i] = INF;
  d[1] = 0;
  int am = 0;
  q.push(1);
  nr[1] = 1;
  inqueue[1] = 1;
  while(!q.empty() && !am){
    int x = q.front();
    q.pop();
    inqueue[x] = 0;
    int l = v[x].size();
    for(i = 0; i < l; ++i){
      y = v[x][i].varf;
      c = v[x][i].cost;
      if(d[x] + c < d[y]){
        d[y] = d[x] + c;
        if(!inqueue[y]){
          q.push(y);
          inqueue[y] = 1;
          nr[y]++;
          if(nr[y] == n)
            am = 1;
        }
      }
    }
  }
  if(am)
    cout << "Ciclu negativ!";
  else
    for(i = 2; i <= n; ++i)
      cout << d[i] << " ";
  return 0;
}