#include <bits/stdc++.h>

using namespace std;

ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

struct Node{
     int node;
     int dist;

     Node(int node, int dist){
          this->node = node;
          this->dist = dist;
     }

     bool operator<(const Node &other) const{
          return this->dist > other.dist;
     }
};

struct Edge{
     int vecin;
     int cost;

     Edge(int vecin, int cost){
          this->vecin = vecin;
          this->cost = cost;
     }
};

list<Edge> adj[10001];
vector<long> dist;
priority_queue<Node> nextStep;
int n, m, a, b, c;

int dijkstra(){
     dist[1] = 0;
     nextStep.push(Node(1,0));
     while(!nextStep.empty()){
          int x = nextStep.top().node;
          nextStep.pop();
          for(list<Edge>::iterator it = adj[x].begin(); it != adj[x].end(); it++){
               if(dist[it->vecin] > dist[x] + it->cost){
                    if(it->vecin == 1 && it->cost < 0){
                         return true;
                    }
                    dist[it->vecin] = dist[x] + it->cost;
                    nextStep.push(Node(it->vecin, dist[it->vecin]));
               }
          }
     }
     return false;
}

int main(){

     fin >> n >> m;
     dist.resize(n+1);
     fill(dist.begin(), dist.end(), LONG_MAX);
     for(int i=0; i<m; i++){
          fin >> a >> b >> c;
          adj[a].push_back(Edge(b,c));
     }
     fin.close();

     if(dijkstra()){
          fout << "Ciclu negativ!";
     } else {
          for(int i=2; i<=n; i++){
               if(dist[i] == LONG_MAX)
                    fout << 0;
               else
                    fout << dist[i];
               fout << " ";
          }
     }
     fout.close();
     return 0;
}