#include <fstream>
#include <vector>
#include <queue>
#define INF 1000000000
using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
vector<  pair<int, long long>   > v[50002];
  //         vf,    cost

long long d[50002];
queue <int> q; // bag in q nodurile la care fac imbunatatire
int cnt[50002], inqueue[50002];
int main()
{
  int n,m, a, b, c;
  fin>>n>>m;
  for(int i=1;i<=m;i++){
    fin>>a>>b>>c; // a--cost c->b
    v[a].push_back( make_pair(b, c) );

  }


  for(int i=1;i<=n;i++){
    d[i] = INF;
  }
  d[1]=0;
  q.push(1);
  inqueue[1]=1;
  cnt[1]=1;
  int amcircuitnegativ=0;




  while( !q.empty() && amcircuitnegativ==0 ){
    int vf = q.front();
    inqueue[vf] = 0;
    q.pop();
    for(vector<pair<int, long long>> :: iterator it = v[vf].begin(); it !=v[vf].end(); it++)
      if(d[vf]+it->second<d[it->first]){
        d[it->first]=d[vf]+it->second;
        cnt[it->first]++;
        if(cnt[it->first]==n)amcircuitnegativ=1;
        if(inqueue[it->first]==0){
          q.push(it->first);
          inqueue[it->first]=1;
        }
      }

  }



   if(amcircuitnegativ ) fout<<"Ciclu negativ!";
      else for(int i=2; i<=n; i++)fout<<d[i]<<' ';

  return 0;
}