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

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

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

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

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

void BellmanFord() {
      vector<int>::iterator it_q;
      vector< pair<int, int> >::iterator it_n;
      vector<int> Edg, Edg2;
       
       
      dist[1] = 0;
      for (int i = 2; i <= n; i++) {
          dist[i] = inf;                         
      }   
      Edg.push_back(1);
      
      for (int i = 1; i < n; i++) {
          bool modified = false;
          for (it_q = Edg.begin(); it_q != Edg.end(); it_q++) {
              int u = *it_q;
              for (it_n = edges[u].begin(); it_n != edges[u].end(); it_n++) {
                  int v = (*it_n).first;
                  int c = (*it_n).second;
                  if (dist[u] + c < dist[v]) {
                      Edg2.push_back(v);            
                      dist[v] = dist[u] + c;                      
                      modified = true;          
                  }
              }
          }
          swap(Edg, Edg2);
          Edg2.clear();
          if (modified == false) {
              break;
          }
      }
      
      bool error = false;
      for (it_q = Edg.begin(); it_q != Edg.end(); it_q++) {
          int u = *it_q;
          for (it_n = edges[u].begin(); it_n != edges[u].end(); it_n++) {
              int v = (*it_n).first;
              int c = (*it_n).second;
              if ((dist[u] + c < dist[v])) {
                  error = true;
                  break;          
              }
          }
          if (error == true) { 
             break;
          }
      }
      
      if (error == true) {
         print_error();
      } else print_();
}

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