#include <cstdio>
#include <vector>
#define nmv 50020
#define INF 0x3f3f3f3f

using namespace std;

vector <pair<long,int> > graph[nmv];
long n,m;
long weight[nmv];
long predecessor[nmv];

void read(){
   scanf("%ld %ld ", &n, &m);
   long x,y;
   int pr;
   while(m--){
     scanf("%ld %ld %d ",&x ,&y ,&pr);
     graph[x].push_back(make_pair(y,pr));
   }
}

void solution(){
  for(long i=2 ; i <= n ; ++i )weight[i]=INF;

  for(long i = 1 ;i < n; ++i ){
    for(vector <pair<long,int> > :: iterator it = graph[i].begin() ; it != graph[i].end() ; ++it )
        if(weight[it->first] > weight[i] + it->second){
           weight[it->first] = weight[i] + it->second;
           predecessor[it->first] = i;
        }
  }

  for(long i=1;i <= n; ++i){
     for(vector <pair<long,int> > :: iterator it = graph[i].begin();it != graph[i].end(); ++it )
       if(weight[it->first] > weight[i] + it->second){
           printf("Ciclu negativ!\n");
           return;
       }
  }

  for(long i=2;i<=n;++i)
    printf("%ld ", weight[i]);
  printf("\n");
}

int main()
{
    freopen("bellmanford.in","r",stdin);
    freopen("bellmanford.out","w",stdout);

    read();
    solution();

    return 0;
}