#include <cstdio>
#include <vector>
#include <queue>
#define MAX 50001
//69 lel
#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;
      //daca putem imbunatati distanta de la fiu cu nodul tata si costul lui
      if (distanta[v] + fiuCost < distanta[fiu]) {
        distanta[fiu] = distanta[v] + fiuCost;
        //daca nu apare in coada, il adaugam ca sa fie parcurs
        if (!inqueue[fiu]) {
          inqueue[fiu] = true;
          q.push(fiu);
          //avem grija daca il vizitam de prea multe ori sa oprim executia
          ++nrcount[fiu];
          if (nrcount[fiu] == n)
            return false;
        }
      }
    }
  }
  return true;
}

int main() {
  //diana be like: jealous.
  freopen("bellmanford.in", "r", stdin);
  freopen("bellmanford.out","w", stdout);

  //citim datele
  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;

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

  //endline: good coding practice
  printf("\n");

  //return strcmp("Rares is god","yes")-1;
  return 0;
}