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

struct Edge {
    int v, cost;
};

int main(){
    ifstream f("bellmanford.in");
    ofstream g("bellmanford.out");
    int N, M;
    f >> N >> M;
    
    // Build an adjacency list (using 1-indexed nodes)
    vector<vector<Edge> > adj(N + 1);
    for (int i = 0; i < M; i++) {
        int u, v, cost;
        f >> u >> v >> cost;
        // Assuming directed edge from u to v
        adj[u].push_back({v, cost});
    }
    
    const int INF = numeric_limits<int>::max();
    vector<int> dist(N + 1, INF);
    vector<bool> inQueue(N + 1, false);
    // Count how many times a node's distance has been updated.
    vector<int> count(N + 1, 0);

    // Source node is 1 (as in the sample)
    dist[1] = 0;
    
    // Use a deque for the SLF improvement.
    deque<int> dq;
    dq.push_back(1);
    inQueue[1] = true;
    
    while (!dq.empty()) {
        int u = dq.front();
        dq.pop_front();
        inQueue[u] = false;
        
        // Process all adjacent edges from u.
        for (const auto &edge : adj[u]) {
            int v = edge.v;
            int cost = edge.cost;
            if (dist[u] != INF && dist[u] + cost < dist[v]) {
                dist[v] = dist[u] + cost;
                // If v is not already in the deque, add it.
                if (!inQueue[v]) {
                    // SLF (Small Label First) optimization:
                    // if the new distance is smaller than that of the front, push at the front.
                    if (!dq.empty() && dist[v] < dist[dq.front()]) {
                        dq.push_front(v);
                    } else {
                        dq.push_back(v);
                    }
                    inQueue[v] = true;
                    count[v]++;
                    // If a node is relaxed N or more times, a negative cycle exists.
                    if (count[v] >= N) {
                        g << "Ciclu negativ!";
                        return 0;
                    }
                }
            }
        }
    }
    
    // Print distances from node 1 to nodes 2 through N.
    for (int i = 2; i <= N; i++) {
        // If a node is unreachable, you could print a special value (e.g., "INF")
        // Here, we assume all nodes are reachable.
        g << dist[i] << " ";
    }
    
    return 0;
}