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

using namespace std;

queue <long> qu;
vector <pair<long,int> > graph[nmv];
long n,m,nom;
long weight[nmv];
long vac[nmv];
bool ah[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(){
   qu.push(1);
   nom=0;
   long x,mn;
   bool pre=false;
   nom=0;
   vac[1]=1;

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

   while(!qu.empty()){
     x = qu.front();
     qu.pop();
     ah[x] = 0;
     for(vector <pair<long,int> > :: iterator it = graph[x].begin(); it != graph[x].end() ; ++it ){
         if(weight[it->first] > weight[x] + it->second){
             weight[it->first] = weight[x] + it->second;
             if(!ah[it->first]){
                 if(vac[it->first]>n)
                     {
                         mn=it->first;
                         break;
                     }
                 qu.push(it->first);
                 ah[it->first]=1;
                 vac[it->first]++;
             }
         }
     }
   }

   if(vac[mn]>n){
      printf("Ciclu negativ!\n");
      return;
   }
   for(long i=2;i <= n; ++i){
       printf("%ld ",weight[i]);
       if(i==n)
        printf("\n");
      }
}

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

    read();
    solution();

    return 0;
}