#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  ){
      vector<int> dist(n+1,INT_MAX) ;
      dist[src] = 0 ; 

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

                          dist[v] = dist[u] + c ; 
                  }
              }
        }
        return dist ; 
}
bool NegCycle(vector<int> &dist ,int n )   
{
     vector<int> cycle(n+1,INT_MAX) ;

       return dist == cycle ; 
}
int main(){

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




    return 0 ; 
}