#include <fstream>
#include <vector>
#include <queue>

#define INF (1 << 30)

using namespace std;

void bellman_ford(int src, std::vector<pair<int, int>> *adj, int n, std::ofstream &out) {
    std::vector<int> dist(n + 1, INF);
    dist[src] = 0;

    std::vector<int> used(n + 1, 0);

    std::queue<int> bellman_ford;
    bellman_ford.push(src);

    while (!bellman_ford.empty()) {
        int node = bellman_ford.front();
        bellman_ford.pop();
        for (auto &neighbour : adj[node]) {
            int next = neighbour.first;
            int weight = neighbour.second;
            if (dist[next] > dist[node] + weight) {
                dist[next] = dist[node] + weight;
                bellman_ford.push(next);
                ++used[next];
                if (used[next] == n) {
                    out << "Ciclu negativ!";
                    return;
                }
            }
        }
    }

    for (int i = 1; i <= n; ++i) {
        if (i != src) {
            if (dist[i] == INF) {
                dist[i] = 0;
            }
            out << dist[i] << ' ';
        }
    }
}

int main() {
    ifstream in("bellmanford.in");
    ofstream out("bellmanford.out");

    int n, m;
    in >> n >> m;

    vector<pair<int, int>> adj[n + 1];

    int i;
    int u, v, weight;

    for (i = 0; i < m; ++i) {
        in >> u >> v >> weight;
        adj[u].push_back({v, weight});
    }

    bellman_ford(1, adj, n, out);

    in.close();
    out.close();
    return 0;
}