#include <bits/stdc++.h>

using namespace std;

constexpr int INF = 0x3f3f3f3f;
constexpr int NMAX = 50003;

ifstream f("bellmanford.in");
ofstream g("bellmanford.out");

int N, M, x, y, c, D[NMAX], L[NMAX];
bool use[NMAX];
vector<pair<int, int>> G[NMAX];
queue<int> Q;
int main()
{
    f >> N >> M;
    for(int i = 1; i <= N; i++) {
      f >> x >> y >> c;
      G[x].push_back({c, y});
    }
    int cn = false;
    for(int i = 2; i <= N; i++)
      D[i] = INF;
    D[1] = 0;
    use[1] = 1;
    Q.push(1);
    while(!Q.empty()) {
      int x = Q.front();
      Q.pop();
      use[x] = false;
      for(auto i : G[x]) {
         int c = i.first, y = i.second;
         if(D[y] > D[x] + c) {
            D[y] = D[x] + c;
            L[y] = L[x] + 1;
            if(L[y] > N) {cn = true; break;}
            if(!use[y])
               Q.push(y), use[y] = true;
         }
      }
    }
    if(cn) {
      g << "Ciclu negativ!\n";
    } else {
      for(int i = 2; i <= N; i++)
         g << D[i] << " ";
      g << "\n";
   }
    return 0;
}