#include <fstream>
#include <bitset>
#include <vector>
#include <queue>

using namespace std;

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

const int NMAX = 50000;
bitset <NMAX + 1> inqueue;
queue <int> q;
vector <pair<int, int>> v[NMAX + 1];
int dist[NMAX + 1];
int viz[NMAX + 1];

int main(){
  int n, m, i, x, y, cost;
  fin >> n >> m;
  for( i = 0; i < m; ++i ){
    fin >> x >> y >> cost;
    v[x].push_back({y, cost});
  }
  for( i = 0; i <= NMAX; ++i )
    dist[i] = (1<<30);
  q.push(1);
  inqueue[1] = 1;
  dist[1] = 0;
  while( !q.empty() ){
    int nod = q.front();
    q.pop();
    inqueue[nod] = 0;
    for( i = 0; i < v[nod].size(); ++i ){
      if( dist[v[nod][i].first] > dist[nod] + v[nod][i].second ){
        dist[v[nod][i].first] = dist[nod] + v[nod][i].second;
        if( !inqueue[v[nod][i].first] ){
          inqueue[v[nod][i].first] = 1;
          q.push(v[nod][i].first);
          ++viz[v[nod][i].first];
          if( viz[v[nod][i].first] > n ) {
            fout << "Ciclu negativ!";
            return 0;
          }
        }
      }
    }
  }
  for( i = 2; i <= n; ++i ){
    if( dist[i] == (1 << 30) )
      dist[i] = 0;
    fout << dist[i] << " ";
  }
  return 0;
}