#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 sw(int &a, int &b) {
     int aux = a;
     a = b; 
     b = aux;     
}

void BellmanFord() {
      vector<int>::iterator it_q;
      vector< pair<int, int> >::iterator it_n;
      vector<int> Edg[2];
       
       
      dist[1] = 0;
      for (int i = 2; i <= n; i++) {
          dist[i] = inf;                         
      }   
      Edg[1].push_back(1);
      
      int nr_old = 0;
      int nr_new = 1;
      
      for (int i = 1; i < n; i++) {
          for (it_q = Edg[nr_new].begin(); it_q != Edg[nr_new].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]) {
                      Edg[nr_old] .push_back(v);            
                      dist[v] = dist[u] + c;             
                  }
              }
          }
          Edg[nr_new].clear();          
          sw(nr_old, nr_new);
      }
      
      bool error = false;
      for (it_q = Edg[nr_new].begin(); it_q != Edg[nr_new].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;
}