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

using namespace std;

ifstream fi("bellmanford.in");
ofstream fo("bellmanford.out");

struct vecin {
  int nod, cost;
}v;

int noduri, muchii, nodc, x, dist[50001], used[50001];
queue<int>q;
vector<vecin>vec[50001];
vector<vecin>::iterator i;

void initdist () {
  for (int i = 2; i <= noduri; i++)
    dist[i] = 2e9;
}

int main () {
  fi >> noduri >> muchii;
  for (int i = 1; i <= muchii; i++)
    fi >> x >> v.nod >> v.cost, vec[x].push_back(v);
  initdist();
  q.push(1);
  while (!q.empty()) {
    nodc = q.front(); q.pop();
    used[nodc]++;
    if (used[nodc] == noduri) {
      fo << "Ciclu negativ!"; return 0;
    }
    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 <= noduri; i++)
    fo << dist[i] << ' ';
  return 0;
}