#include <fstream>
#include <vector>
#define maxn 50100
#define inf 2000000000

using namespace std;

struct adat
{
  long kezd,veg,ut;
} a;

long n,m,dist[maxn];
vector<adat> v;
long i,x,y,cost;
ifstream in("bellmanford.in");
ofstream out("bellmanford.out");

int bellman()
{
  //itt
  long l=1,k,h=n-1,g=m-1;
  short ok=1;
  dist[1]=0;
  while (l<=h)//&&ok==1)
  {
    //ok=0;
    for (k=0;k<=g;++k)
    if (dist[v[k].veg]>dist[v[k].kezd]+v[k].ut)
       {
        dist[v[k].veg]=dist[v[k].kezd]+v[k].ut;
        //ok=1;
       }
    ++l;
  }

  return 0;
}

int negative()
{
    //negativ kor
    long k,h=m-1;
    for (k=0;k<=h;++k)
    if (dist[v[k].veg]>dist[v[k].kezd]+v[k].ut)
       return 1;

    return 0;
}

int main()
{
  in >> n >> m;
  for (i=0;i<=n;++i) dist[i]=inf;
  for (i=1;i<=m;++i)
  {
    in >> x >> y >> cost;
    v.push_back((adat){x,y,cost});
  }

  bellman();

  if (negative()==1) out << "Ciclu negativ!";
  else
  for (i=2;i<=n;++i) out << dist[i] << " ";

  in.close();
  out.close();

  return 0;
}