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

#define INF (1 << 30)

struct edge {

    int node;
    int weight;
    int used;

    edge(int node, int weight, int used) {
        this -> node = node;
        this -> weight = weight;
        this -> used = used;
    }

};

void bellman_ford(int src, std::vector<struct edge> *adj, int n, int m, std::ofstream &out) {
    std::vector<int> dist(n + 1, INF);
    dist[src] = 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]) {
            if (dist[neighbour.node] > dist[node] + neighbour.weight) {
                dist[neighbour.node] = dist[node] + neighbour.weight;
                bellman_ford.push(neighbour.node);
                ++neighbour.used;
                if (neighbour.used == m) {
                    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() {
    std::ifstream in("bellmanford.in");
    std::ofstream out("bellmanford.out");

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

    std::vector<struct edge> adj[n + 1];

    int i;
    int u, v, weight;

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

    bellman_ford(1, adj, n, m, out);

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