#include <stdio.h>
#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()
{
  freopen("bellmanford.in","r",stdin);
  freopen("bellmanford.out","w",stdout);

  long i,x,y,cost;
  scanf("%ld%ld\n",&n,&m);
  for (i=0;i<=n;++i) dist[i]=2000000;
  for (i=1;i<=m;++i)
  {
    scanf("%ld%ld%ld\n",&x,&y,&cost);
    a.kezd=x;
    a.veg=y;
    a.ut=cost;
    v.push_back(a);
  }

  bellman();

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


  return 0;
}