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

using namespace std;

typedef pair<int, int> muchie;

struct fmuchie {
   int u, v, c;
};

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

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

vector<fmuchie> edges(MMAX);

int N, M;

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

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

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

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

   D[1] = 0;

   for (int k = 1; k <= N; ++k) {
      for (int i = 1; i <= M; ++i) {
         fmuchie e = edges[i];
         int u = e.u;
         int v = e.v;
         int c = e.c;

         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 (int i = 1; i <= M; ++i) {
         fmuchie e = edges[i];
         int u = e.u;
         int v = e.v;
         int c = e.c;

         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;
}