#include <fstream>
#include <vector>
#include <queue>

using namespace std;

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

int main() {

  int n, m;
  cin >> n >> m;
  
  vector < vector < pair < int, int > > > gr(n + 1);
  for (int i = 1; i <= m; i ++) {

    int x, y, c;
    cin >> x >> y >> c;
    gr[x].push_back({c, y});
  }

  queue < int > q;
  vector < int > dist(n + 1, 2e9);
  vector < int > frecv(n + 1); 
  dist[1] = 0;
  q.push(1);
  while (not q.empty()) {

    int cur = q.front();
    q.pop();

    if (++ frecv[cur] == n and dist[cur] < 0) {
      cout << "Ciclu negativ!\n";
      return 0;
    }

    for (auto x : gr[cur]) {
      if (dist[x.second] > dist[cur] + x.first) {
        dist[x.second] = dist[cur] + x.first;
        q.push(x.second);
      }
    }
  }

  for (int i = 2; i <= n; i ++) {
    cout << dist[i] << ' ';
  }
}