#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#define INF 0x3f3f3f3f
#define DIM 50005
using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");

int n,m;
vector <pair<int,int> > graf[DIM];
vector <int> v;
queue <int> coada;
int d[DIM];
int viz[DIM];
int esteincoada[DIM];

bool bellmanford(int s)
{
 for(int i=1;i<=n;i++)
 {viz[i]=0;
 esteincoada[i]=0;
 d[i]=INF;
 }

 d[s]=0;
 coada.push(s);
 esteincoada[s]=1;

 while(!coada.empty())
 {int nodcurent=coada.front();
  viz[nodcurent]++;
  if(viz[nodcurent]>=n) return false;
  coada.pop();
  esteincoada[nodcurent]=0;

  for(size_t i=0;i<graf[nodcurent].size();i++)
  {int vecin=graf[nodcurent][i].first;
   int cost=graf[nodcurent][i].second;
   if(d[nodcurent]+cost<d[vecin])
   {d[vecin]=d[nodcurent]+cost;
    if(!esteincoada[vecin])
        coada.push(vecin);

   }

  }

 }

 return true;

}

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

 }

 if(bellmanford(1))
 {
  for(int i=2;i<=n;i++)
        g<<d[i]<<" ";
 }

 else g<<"Ciclu negativ!";

    return 0;
}