#include <fstream>
#include <vector>
#include <climits>
#include <queue>

using std::vector;

struct Node{
   int v, w;
};

int main(){
   std::ifstream in("bellmanford.in");
   std::ofstream out("bellmanford.out");
   int n, m;
   bool negativeCycle = false;
   in >> n >> m;
   std::queue<int> q;
   q.push(0);
   vector<vector<Node>> graph(n, vector<Node>());
   vector<int> dist(n, INT_MAX), count(n, 0);
   vector<bool> inQ(n, false);
   dist[0] = 0;
   // beolvasás
   for(int i = 0; i < m; i++){
      int u, v, w;
      in >> u >> v >> w;
      u--; v--;
      graph[u].push_back({v, w});
   }
   // algoritmus
   while(!q.empty()){
      int front = q.front();
      inQ[front] = false;
      q.pop();
      for(auto i : graph[front]){
         if(dist[front] != INT_MAX && dist[front] + i.w < dist[i.v]){
            dist[i.v] = dist[front] + i.w;
            if(!inQ[i.v]){
               inQ[i.v] = true;
               q.push(i.v);
               if(count[i.v] > n){
                  negativeCycle = true;
                  while(!q.empty()) q.pop();
                  break;
               }
               count[i.v]++;
            }
         }
      }
   }

   if(negativeCycle)
      out << "Ciclu negativ!";
   else
      for(int i = 1; i < n; i++)
         out << dist[i] << ' ';
   in.close();
   out.close();
}