#include <bits/stdc++.h>

#define N 50005
#define oo 0x3f3f3f3f

using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
int n, m;
vector<pair<int, int>> graf[N];
int nr[N];
bool viz[N];
int dp[N];

void read() {
  f>>n>>m;
  int x, y, z;
  for(int i = 1;i <= m;++i) {
    f>>x>>y>>z;
    graf[x].push_back(make_pair(y, z));
  }
}

void solve() {
  queue<int> q;
  q.push(1);

  memset(viz, false, sizeof(viz));
  memset(dp, oo, sizeof(dp));
  viz[1] = true;
  dp[1] = 0;

  while(!q.empty()) {
    int node = q.front();
  
    for(const auto& pr : graf[node]) {
      if(dp[pr.first] > dp[node] + pr.second) {
        if(!viz[pr.first]) {
          q.push(pr.first);
        }
        viz[pr.first] = true;
        dp[pr.first] = dp[node] + pr.second;
        nr[pr.first]++;
        if(nr[pr.first] >= n) {
          g<<"Ciclu negativ!";
          return;
        }
      }
    }
    
    q.pop();
    viz[node] = false;
  }
  for(int i = 2;i <= n;++i) {
    g<<dp[i]<<" ";
  }
}

int main() {
  read();
  solve();
  return 0;
}