#include <fstream>
#include <vector>
#include <queue>
using namespace std;

#define inf (1 << 30)

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

int n, m, neg_cycle;
vector<vector<pair<int, int>>> G;
vector<int> D;
vector<bool> IQ;

struct compare {
  bool operator() (int x, int y) {
    return D[x] > D[y];
  }
};

void bellman_ford(int k) {
  queue<int> Q;
  vector<int> C(n + 1, 0);
  
  Q.push(k);
  IQ[k] = 1;
  D[k] = 0;
  
  while (!Q.empty() && !neg_cycle) {
    int x = Q.front();
    Q.pop();
    IQ[x] = 0;
    
    for (auto y : G[x]) {
      int v = y.first;
      int c = y.second;
      
      if (D[x] + c < D[v]) {
        D[v] = D[x] + c;
        
        if (IQ[v] == 0) {
          if (C[v] > n) neg_cycle = 1;
          else Q.push(v), IQ[v] = 1, ++C[v];
        }
      }
    }
  }
}

int main() {
  cin >> n >> m;
  G = vector<vector<pair<int, int>>> (n + 1);
  D = vector<int> (n + 1, inf);
  IQ = vector<bool> (n + 1, 0);
  
  for (int i = 1, a, b, c; i <= m; ++i)
    cin >> a >> b >> c, G[a].push_back(make_pair(b, c));
    
  bellman_ford(1);
  
  if (!neg_cycle) {
    for (int i = 2; i <= n; ++i)
      cout << D[i] << " ";
  } else cout << "Ciclu negativ!";
  
  cin.close();
  cout.close();
  return 0;
}