#include<stdio.h>
#include<vector>
#include<deque>
#define inf 1000000000
using namespace std;
struct nod{ int y,cost;};

vector<nod> a[50001];
deque<int> coada;
int nr_noduri,nr_muchii,dist[50001],apar[50001];

int bellmanford()
{
    dist[1]=0;
     for(int i=2;i<=nr_noduri;++i)
       dist[i]=inf;
    coada.push_back(1);
    while(!coada.empty())
    { int x=coada.front();
         if(dist[x]!=inf)
           for (int i=0;i<a[x].size();++i)
               {
                   if (dist[a[x][i].y]>dist[x]+a[x][i].cost)
                     {
                       dist[a[x][i].y]=dist[x]+a[x][i].cost;
                       coada.push_back(a[x][i].y);
                       if( ++apar[a[x][i].y] > nr_noduri-1)
                          return 1;}
           }
       coada.pop_front();
   }
return 0;
}

int main()
{ nod t;
int r;
  freopen("bellmanford.in","r",stdin);
  freopen("bellmanford.out","w",stdout);
  scanf("%d%d",&nr_noduri,&nr_muchii);
  for (int i=1;i<=nr_muchii;++i)
   {
        scanf("%d%d%d",&r,&t.y,&t.cost);
        a[r].push_back(t);
   }
  if (bellmanford())
   printf("Ciclu negativ!");
   else
    for(int i=2;i<=nr_noduri;++i)
      printf("%d ",dist[i]);
 return 0;
}