#include <stdio.h>
#include <vector>
#include <set>
#define NMAX 50001
#define inf 50000001
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;
      set<int> Edg[2];      
             
      dist[1] = 0;
      for (int i = 2; i <= n; i++) {
          dist[i] = inf;                         
      }   
      Edg[1].insert(1); 
      
      int nr_old = 0;
      int nr_new = 1;
      
      for (int i = 1; i <= n; i++) {
          while (Edg[nr_new].size() > 0) {
              int u = *Edg[nr_new].begin();
              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].insert(v); 
                      dist[v] = dist[u] + c;             
                  }
              }
              Edg[nr_new].erase(Edg[nr_new].begin());
          }          
          sw(nr_old, nr_new);
      }                 
      
      if (Edg[nr_new].size() > 0) {
         print_error();
      } else {
         print_();
      }
}

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