#include <stdio.h>
#include <vector>
#include <stack>
#include <fstream>

#define NMAX 50001
#define MMAX 250001
#define inf 250000001
using namespace std;

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

void read_() {
     int source, dest, cost;
     
     ifstream fin("bellmanford.in");    
     fin >> n >> m;
     for (int i = 0; i < m; i++) {
         fin >> source >> dest >> cost;
         edges[source].push_back(make_pair(dest, cost)); 
     }     
     
     fin.close();
}

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;
      stack<int> Edg[2];
       
       
      dist[1] = 0;
      for (int i = 2; i <= n; i++) {
          dist[i] = inf;                         
      }   
      Edg[1].push(1); 
      
      int nr_old = 0;
      int nr_new = 1;
      
      for (int i = 1; i <= n; i++) {
          while (Edg[nr_new].empty() == false) {
              int u = Edg[nr_new].top();
              Edg[nr_new].pop();
              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(v);            
                      dist[v] = dist[u] + c;             
                  }
              }
          }          
          sw(nr_old, nr_new);
      }                 
      
      if (Edg[nr_new].empty() == false) {
         print_error();
      } else {
         print_();
      }
}

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