// Bellman - O(N*M)
#include <fstream>
#include <vector>
#include <queue>
#include <bitset>
#define Nmax 50009
#define y first
#define c second
#define oo 2000000000

using namespace std;

ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
typedef pair<int,int> PP;

int N, M, d[Nmax], used[Nmax], x, y, c;
vector < PP > G[Nmax];

queue < int > Q;
bitset < Nmax > inQ;

/* intoarce 1 daca se poate construi  vectorul de distante
   intoarece 0 daca se gaseste un cilcu de cost negativ */
int Bellmanford(const int& S){
  /* init */
  for(int i = 1; i <= N; ++i) {
    d[i] = oo;
  }

  Q.push(S);
  d[S] = 0; 
  inQ[S] = 1;

  for(;  !Q.empty();  Q.pop()) {
      int node = Q.front();
      
      inQ[node] = 0;
      ++used[node];
      
      if (used[node] == N) {
        return 0; /* ciclu de cost negativ */
      }

      for (vector<PP>::iterator it = G[node].begin(); it != G[node].end(); ++it) {
        if(d[it->y] > d[node]+it->c){
          d[it->y] = d[node]+it->c;
          if (!inQ[it->y]) {
            Q.push(it->y);
            inQ[it->y] = 1;
          }
        }
      }
  }
  return 1; /* Nu are ciclu de cost negativ */
}

int main() {
  f >> N >> M;

  for(int i = 1; i <= M; ++i) {
    int x, y, c;
    f >> x >> y >> c;
    G[x].push_back(PP(y,c));
    /* pt neorientat adauga */
    /* G[y].push_back(PP(x,c)); */
  }

  if(Bellmanford(1) == 0){
    g << "Ciclu negativ!" << '\n';
  } else {
      for(int i = 2; i <= N; ++i) {
        g << d[i] << ' ';
      }
      g<<'\n';
  }

  f.close();g.close();
  return 0;
}