#include <cstdio>
#include <vector>
#include <queue>
#define MAX 50001
#define INF (1<<6<<9<<6<<9)
using namespace std;

struct nod{
  int varf, cost;
  nod(int varf, int cost) { this->varf = varf; this->cost = cost; }
};

vector<nod> a[MAX];
queue<int> q;

int distanta[MAX];
bool inqueue[MAX];
int nrcount[MAX];

int n, m;

int BellmanFord(int x) {
  //pornim din nodul x, distanta lui fata de celalte noduri e evident 0
  distanta[x] = 0;
  //il adaugam in coada si ne asiguram ca e vizitat
  inqueue[x] = true;
  q.push(x);

  int fiu,fiuCost;

  //parcurgem coada si scoatem primul element
  while (!q.empty()) {
    int v = q.front();
    q.pop();
    inqueue[v] = false;
    //ii parcurgem muchiile
    for (vector<nod>::iterator i = a[v].begin(); i != a[v].end(); i++) {
      fiu = i->varf;
      fiuCost = i->cost;
      if (distanta[v] + fiuCost < distanta[fiu]) {
        distanta[fiu] = distanta[v] + fiuCost;
        if (!inqueue[fiu]) {
          inqueue[fiu] = true;
          q.push(fiu);
          ++nrcount[fiu];
          if (nrcount[fiu] == n)
            return false;
        }
      }
    }
  }
  return true;
}

int main() {
  freopen("bellmanford.in", "r", stdin);
  freopen("bellmanford.out","w", stdout);


  scanf("%d %d", &n, &m);
  int x,y,c;
  for (int i = 1; i <= m; i++)
    if (scanf("%d %d %d", &x, &y, &c)!=EOF)
      a[x].push_back(nod(y, c));

  //setam distanta pe infinit, toate muchiile vor fi bune
  for (int i = 1; i <= n; i++)
    distanta[i] = INF;

  if (!BellmanFord(1))
    printf("Ciclu negativ!");
  else
    for (int i = 2; i <= n; i++)
      printf("%d ",distanta[i]);

  printf("\n");
  return 0;
}