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

using namespace std;

struct vecin {
  int nod, cost;
};

int n, m, x, y, cost, dist[50005], f[50001];
vector<vecin>vec[50005];
queue<int>q;

int main () {
  ifstream fi("bellmanford.in");
  ofstream fo("bellmanford.out");
  fi >> n >> m; vecin v;
  for (int i = 1; i <= n; i++)
    dist[i] = 2e9;
  for (int i = 1; i <= m; i++)
    fi >> x >> v.nod >> v.cost, vec[x].push_back(v);
  q.push(1); dist[1] = 0;
  while (!q.empty()) {
    int nodc = q.front(); q.pop();
    f[nodc]++;
    if (f[nodc] == n) {
      fo << "Ciclu negativ!";
      return 0;
    }
    vector<vecin>::iterator i;
    for (i = vec[nodc].begin(); i < vec[nodc].end(); i++)
      if (dist[(*i).nod] > dist[nodc]+(*i).cost)
        dist[(*i).nod] = dist[nodc]+(*i).cost, q.push((*i).nod);
  }
  for (int i = 2; i <= n; i++)
    fo << dist[i] << ' ';
  return 0;
}