#include <fstream> 
 
using namespace std; 
 
 
#define INF 1000000000 
 
 
long x[250010], y[250010], c[250010], cost[50010], n, m, i, muchie; 
 
 
int main() { 
    
ifstream f("bellmanford.in"); 
    
ofstream h("bellmanford.out"); 
     
 
    
f>>n>>m; 
    
muchie = m; 
 
 
    
for (i = 1; i <= n; ++i) cost[i] = INF; 
    
cost[1] = 0; 
     
 
    
for (i = 1; i <= m; ++i) f>>x[i]>>y[i]>>c[i]; 
     
 
    
long H = 0; 
    
long aux = 1; 
    
while (aux && H < n + 2) { 
        
aux = 0; 
        
++H; 
        
for (i = 1; i <= m; ++i) { 
            
if (cost[x[i]] + c[i] < cost[y[i]]) { 
                
cost[y[i]] = cost[x[i]] + c[i]; 
                
aux = 1; 
            
} 
        
} 
    
} 
     
 
    
if (H >= n + 2) { 
        
h<<"Ciclu negativ!\n"; 
    
} else { 
        
for (i = 2; i <= n; ++i) { 
            
h<<cost[i]<<" "; 
        
} 
    
} 
         
 
    
return 0; 
}