#include<fstream>
#include<vector>
#include<climits>
#include<utility>
using namespace std ; 
ifstream cin("bellmanford.in");
ofstream cout("bellmanford.out");
vector<int> BF (int src , vector<vector<int> > &edges , int n ,int  m, bool &neg   ){
      vector<int> dist(n+1,INT_MAX) ;
      dist[src] = 0 ; 

        for(int k = 1  ; k <= n - 1  ; k  ++ ){
              
              for(int i  = 1 ; i  <= m ; i ++ ){
                   
                  int u = edges[i][0];
                  int v = edges[i][1];
                  int c = edges[i][2];
                  if(dist[u]!=INT_MAX && dist[v] > dist[u] + c ){
                       

                          dist[v] = dist[u] + c ; 
                  }
              }
        }
          for(int i = 1 ; i <= m ; i ++ ){
                 
                  int u = edges[i][0];
                  int v = edges[i][1];
                  int c = edges[i][2];
                  if(dist[u]!=INT_MAX && dist[v] > dist[u] + c ){
                      neg = true ; 
                      break;
                  }
          }
          
        return dist ; 
}

int main(){

    
    int x , y , n , m , c ; 
     cin>>n>>m;
         vector<vector<int> > edges(m+1,vector<int>(3));
           for(int i = 1 ; i <= m ; i ++ ){
                 cin>>edges[i][0]>>edges[i][1]>>edges[i][2];
           }
           bool neg ;
           vector<int> dist = BF(1,edges,n,m,neg);
         
            
                int count = 0 ; 
                      for(int i = 2 ; i <= n ; i ++ )
                    if(dist[i] == INT_MAX)
                      count ++ ; 
                     if(neg  ){
                        cout<<"Ciclu negativ";
                     }else{

                     
                         for(int i = 2 ; i <= n ; i ++ )
                          if(dist[i]!=INT_MAX)
                          cout<<dist[i]<< ' ';
                     }




    return 0 ; 
}