#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

#define NMAX 50002
#define INF 100000002

struct edge {
  int nod, cost;
};
vector<edge> graf[NMAX];

queue<int> q;

int dist[NMAX];
int flag[NMAX];
int cnt[NMAX];

int n;

int bf(int nod) {
  int now, i, vecin;
  
  q.push(nod);
  dist[nod] = 0;
  cnt[nod]++;
  flag[nod] = 1;
  
  now = q.front();
  while (!q.empty() && cnt[now]<n) {
    for (i=0; i<graf[now].size(); i++) {
      vecin = graf[now][i].nod;
      if (dist[vecin] > dist[now]+graf[now][i].cost) {
        dist[vecin] = dist[now]+graf[now][i].cost;
        cnt[vecin]++;
        
        if (flag[vecin]==0) {
          q.push(vecin);
          flag[vecin] = 1;
        }
      }
    }
    
    flag[now] = 0;
    q.pop();
    now = q.front();
  }
  
  if (!q.empty()) {
    return 1;
  }
  return 0;
}

int main() {
    ifstream fin("bellmanford.in");
    ofstream fout("bellmanford.out");
    
    int m, a, b, cost, i, ok;
    
    fin >> n >> m;
    
    for (i=0; i<m; i++) {
      fin >> a >> b >> cost;
      graf[a].push_back({b, cost});
    }
    
    for (i=1; i<=n; i++) {
      dist[i] = INF;
    }
    
    ok = bf(1);
    
    if (ok==1) {
      fout << "Ciclu negativ!";
    } else {
      for (i=2; i<=n; i++) {
        fout << dist[i] << ' ';
      }
    }
    
    fin.close();
    fout.close();
    return 0;
}