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

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];
queue<int> Q;
int D[NMAX];
int P[NMAX];

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) {
      int u, v, c;
      scanf("%d %d %d", &u, &v, &c);
      G[u].push_back(make_pair(v,c));
   }

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

   D[1] = 0;
   Q.push(1);

   while (!Q.empty()) {
      int node = Q.front();
      Q.pop();
      for (muchie m : G[node]) {
         int u = node;
         int v = m.first;
         int c = m.second;
         if (D[u] + c < D[v]) {
            D[v] = D[u] + c;
            Q.push(v);
         }
      }
   }

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