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

using namespace std;

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

long n,m,dist[maxn];
vector<adat> v;


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()
{
  ifstream in("bellmanford.in");
  ofstream out("bellmanford.out");

  long i,x,y,cost;
  in >> n >> m;
  for (i=0;i<=n;++i) dist[i]=2000000;
  for (i=1;i<=m;++i)
  {
    in >> x >> y >> cost;
    a.kezd=x;
    a.veg=y;
    a.ut=cost;
    v.push_back(a);
  }

  bellman();

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

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


  return 0;
}