#include <stdio.h>
#define MAXN 50000
#define MAXM 250000
#define INF 2000000000
int ult[MAXN], nod[2 * MAXM], next[2 * MAXM], cost[2 * MAXM];
int nr[MAXM], dist[MAXN], q[MAXN];
char inq[MAXN];

inline int add(int *x, int n){
  (*x)++;
  if(*x >= n)
    (*x) -= n;
}

inline char befo(int n){
  int st = 0, dr = 1, poz;
  q[0] = 0;
  dist[0] = 0;  inq[0] = 1;
  while(st != dr){
    poz = ult[q[st]];
    while(poz != -1){
      if(dist[nod[poz]] > dist[q[st]] + cost[poz]){
        dist[nod[poz]] = dist[q[st]] + cost[poz];
        nr[poz]++;
        if(nr[poz] >= n)
          return 0;
        if(!inq[nod[poz]]){
          q[dr] = nod[poz];
          inq[nod[poz]] = 1;
          add(&dr, n);
        }
      }
      poz = next[poz];
    }
    inq[q[st]] = 0;
    add(&st, n);
  }
  return 1;
}

int main(){
  FILE *in = fopen("bellmanford.in", "r");
  int n, m, i, x, y, c, dr = 0;
  fscanf(in, "%d%d", &n, &m);
  for(i = 0; i < n; i++)
    ult[i] = -1;
  for(i = 0; i < m; i++){
    fscanf(in, "%d%d%d", &x, &y, &c);
    x--;  y--;
    nod[dr] = y;
    next[dr] = ult[x];
    cost[dr] = c;
    ult[x] = dr;
    dr++;
  }
  fclose(in);
  for(i = 0; i < n; i++)
    dist[i] = INF;
  char rez = befo(n);
  FILE *out = fopen("bellmanford.out", "w");
  if(rez == 0)
    fprintf(out, "Ciclu negativ!");
  else
    for(i = 1; i < n; i++)
      fprintf(out, "%d ", dist[i]);
  fclose(out);
  return 0;
}