#include <stdio.h>
#include <vector>
#include <utility>

using namespace std;

typedef pair<int, int> muchie;

const int NMAX = 50005;
const int MMAX = 250005;
const int WMAX = 1005;

vector<muchie> G[NMAX];
int D[NMAX];
int P[NMAX];

int N, M;

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

   scanf("%d %d", &N, &M);

   for (int i = 0; i < M; ++i) {
      int x,y,c;
      scanf("%d %d %d", &x, &y, &c);
      G[x].push_back(make_pair(y,c));
   }

   for (int i = 1; i <= N; ++i) {
      D[i] = WMAX;
      P[i] = -1;
   }

   D[1] = 0;

   for (int k = 1; k < N; ++k) {
      for (int i = 1; i <= N; ++i) {
         for (muchie m : G[i]) {
            int u = i;
            int v = m.first;
            int c = m.second;

            if (D[u] + c < D[v]) {
               D[v] = D[u] + c;
            }
         }
      }
   }

   bool ciclu_negativ = false;
   for (int i = 1; i <= N; ++i) {
      if (ciclu_negativ) {
         break;
      }
      for (muchie m : G[i]) {
         int u = i;
         int v = m.first;
         int c = m.second;

         if (D[u] + c < D[v]) {
            printf("Ciclu negativ!\n");
            ciclu_negativ = true;
            break;
         }
      }
   }

   if (!ciclu_negativ) {
      for (int i = 2; i <= N; ++i) {
         printf("%d ", D[i]);
      }
   }


   fclose(stdin);
   fclose(stdout);
   return 0;
}