#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 5e4;
const int MMAX = 25e4;

struct nod{
    int vecin, cost;
};

vector<nod> adj[NMAX+1];
bool inQ[NMAX+1];
int cntQ[NMAX+1], dist[NMAX+1];

int n, m;

bool coaie_esti_prost = true;

void belly(int x){
    
    queue<int> q;
    
    q.push(x);
    
    while(!q.empty()){
        
        int currNode = q.front();
        q.pop();
        inQ[currNode] = 0;
        
        if(cntQ[currNode] >= n){
            
            coaie_esti_prost = false;
            return;
            
        }
        
        for(auto [vecin, cost] : adj[currNode]){
            
            if(dist[currNode] + cost < dist[vecin]){
                
                dist[vecin] = cost + dist[currNode];
                
                if(!inQ[vecin])
                    q.push(vecin), inQ[vecin] = true;
                    
                cntQ[vecin] ++;
                
            }
            
        }
        
    }
    
}

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});
        
        
    }
    
    fill(dist + 2, dist + 1 + NMAX, 2e9);
    
    belly(1);
    
    if(coaie_esti_prost == false){
        
        g << "Ciclu negativ!";
        return 0;
        
    }
    
    for(int i=2; i<=n; i++)
        g << dist[i] << ' ';

    return 0;
}