#include <fstream>
#include <vector>
#include <queue>
#define NMAX 500005
#define INF 1000000000

using namespace std;

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

int n, m, x0=1;

vector<pair<int, int> > G[NMAX];
queue <int> C;
int dmin[NMAX], nr[NMAX];

bool negativ=false;

void citire(){
  fin >> n >> m;
  int x, y, c;
  for(int i=1; i<=m; i++){
    fin >> x >> y >> c;
    G[x].push_back({y, c});
  }
}

void bellman_ford(){
  vector <pair<int, int> > ::iterator it;
  int x;
  for(int i=1; i<=n; i++)
    dmin[i] = INF;
  dmin[x0] = 0;
  C.push(x0);
  while(!C.empty() && !negativ){
    x = C.front();
    C.pop();
    for(it = G[x].begin(); it!=G[x].end(); it++)
      if(dmin[it->first] > dmin[x]+it->second){
        dmin[it->first] = dmin[x]+it->second;
        nr[it->first]++;
        C.push(it->first);
        if(nr[it->first] > n)
          negativ = true;
      }
  }
}

void afisare(){
  if(negativ == true)
    fout << "Ciclu negativ!";
  else
    for(int i=2; i<=n; i++)
      fout << dmin[i] << ' ';
}

int main()
{
    citire();
    bellman_ford();
    afisare();
    return 0;
}