#include <stdio.h>
#include <vector>
#define NMAX 50001
#define MMAX 250001
#define inf 2147483640
using namespace std;

typedef struct {
     int source;
     int dest;
     int cost;
} edge;

vector<edge> edges;
int dist[NMAX];
int n, m;

void read_() {
     int s, d, c;    
     scanf("%d%d", &n, &m);
     for (int i = 0; i < m; i++) {
         scanf("%d%d%d", &s, &d, &c);
         edge e;
         e.source = s;
         e.dest = d;
         e.cost = c;
         edges.push_back(e); 
     }     
}

void print_error() {
     printf("Ciclu negativ!");
}

void print_() {
     for (int i = 2; i <= n; i++) {
         printf("%d ", dist[i]);
     }
}     

void BellmanFord() {
      vector<edge>::iterator it;
      
      dist[1] = 0;
      for (int i = 2; i <= n; i++) {
          dist[i] = inf;                         
      }   
      
      for (int i = 1; i < n; i++) {
          bool modified = false;
          for (it = edges.begin(); it != edges.end(); it++) {
              int u = (*it).source;
              int v = (*it).dest;
              if ((dist[u] + (*it).cost < dist[v])) {
                 dist[v] = dist[u] + (*it).cost;  
                 modified = true;          
              }
          }
          if (modified == false) {
              break;
          }
      }
      
      bool error = false;
      for (it = edges.begin(); it != edges.end(); it++) {
          int u = (*it).source;
          int v = (*it).dest;
          if ((dist[u] + (*it).cost < dist[v])) {
             error = true;            
          }
      }
      
      if (error == true) {
         print_error();
      } else print_();
}

int main() {
    freopen("bellmanford.in", "r", stdin);
    freopen("bellmanford.out", "w", stdout);
    
    read_();
    BellmanFord();
    
    return 0;
}