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

using std::vector;

struct Node{
   int u, v, w;
};

int main(){
   std::ifstream in("bellmanford.in");
   std::ofstream out("bellmanford.out");
   int n, m;
   in >> n >> m;
   vector<Node> graph;
   vector<int> dist(n, INT_MAX);
   dist[0] = 0;
   // beolvasás
   for(int i = 0; i < m; i++){
      int u, v, w;
      in >> u >> v >> w;
      u--; v--;
      graph.push_back({u, v, w});
   }
   // algoritmus
   for(int k = 1; k < n; k++)
      for(auto i : graph)
         if(i.w != INT_MAX && dist[i.u] + i.w < dist[i.v])
            dist[i.v] = dist[i.u] + i.w;

   bool megvaltozott = 0;
   
   for(auto i : graph)
      if(i.w != INT_MAX && dist[i.u] + i.w < dist[i.v])
         megvaltozott = true;

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