#include <bits/stdc++.h>

using namespace std;

ifstream f ("bellmanford.in");
ofstream g ("bellmanford.out");

const int NMAX = 5e4;
int dist[NMAX + 1], cntQ[NMAX + 1];
bool inQ[NMAX + 1];
vector<pair<int, int>> adj[NMAX + 1];

int n, m;
bool e_ciclu;
queue<int> q;

void belly(int x){
    
    q.push(x);
    
    while(!q.empty()){
        
        int nod = q.front();
        q.pop();
        
        if(cntQ[nod] >= n){
            
            e_ciclu = true;
            return;
            
        }
        
        inQ[nod] = false;
        
        for(auto next : adj[nod]){
            
            if(dist[next.first] > dist[nod] + next.second){
            
                dist[next.first] = dist[nod] + next.second;
            
                if(!inQ[next.first])
                    inQ[next.first] = true, q.push(next.first);
                
                cntQ[next.first] ++;
            }
            
        }
        
    }
    
}

int main()
{
    f >> n >> m;
    
    for(int i=1; i<=m; i++){
        
        int x, y, cost;
        f >> x >> y >> cost;
        
        adj[x].push_back({y, cost});
        
        
    }
    
    for(int i=2; i<=NMAX; i++)
        dist[i] = 2e9;
        
    belly(1);
    
    if(e_ciclu){
        
        g << "Ciclu negativ!";
        
        return 0;
        
    }
    
    for(int i=2; i<=n; i++)
        g << dist[i] << ' ';
    
    return 0;
}