#include <vector>
#include <deque>
#include <limits>
#include <fstream>
#include <ios>
using namespace std;

struct alignas(64) Edge {  // Cache-aligned structure
    int v, cost;
};

int main() {
    // Optimize I/O operations
    ios_base::sync_with_stdio(false);
    
    ifstream f("bellmanford.in");
    ofstream g("bellmanford.out");
    
    int N, M;
    f >> N >> M;
    
    // Pre-allocate memory to avoid costly reallocations
    vector<vector<Edge>> adj(N + 1);
    for (int i = 1; i <= N; i++) {
        adj[i].reserve(16);  // Reasonable estimate to avoid resizing
    }
    
    for (int i = 0, u, v, cost; i < M; i++) {
        f >> u >> v >> cost;
        adj[u].push_back({v, cost});
    }
    
    f.close();  // Close input file to free resources
    
    const int INF = numeric_limits<int>::max();
    vector<int> dist(N + 1, INF);
    vector<uint8_t> inQueue(N + 1, 0);  // Use uint8_t instead of bool for better memory access
    vector<int> count(N + 1, 0);

    dist[1] = 0;
    
    deque<int> dq;
    dq.push_back(1);
    inQueue[1] = 1;
    
    bool negCycle = false;
    bool improved = true;
    int iterations = 0;
    
    // Main algorithm loop with multiple early termination conditions
    while (!dq.empty() && improved && !negCycle && iterations < N) {
        improved = false;
        iterations++;
        
        int size = dq.size();
        for (int i = 0; i < size && !negCycle; i++) {
            int u = dq.front();
            dq.pop_front();
            inQueue[u] = 0;
            
            if (dist[u] == INF) continue;  // Skip unreachable nodes
            
            for (const Edge& edge : adj[u]) {
                int v = edge.v;
                int cost = edge.cost;
                
                int newDist = dist[u] + cost;  // Calculate once
                if (newDist < dist[v]) {
                    dist[v] = newDist;
                    improved = true;
                    
                    if (!inQueue[v]) {
                        // SLF (Small Label First) optimization
                        if (!dq.empty() && newDist < dist[dq.front()]) {
                            dq.push_front(v);
                        } else {
                            dq.push_back(v);
                        }
                        inQueue[v] = 1;
                        
                        if (++count[v] >= N) {
                            negCycle = true;
                            break;
                        }
                    }
                }
            }
        }
    }
    
    if (negCycle) {
        g << "Ciclu negativ!";
    } else {
        for (int i = 2; i <= N; i++) {
            g << dist[i] << " ";
        }
    }
    
    return 0;
}