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

#define INF (1 << 30)

using namespace std;

void bellman_ford(int src, vector<tuple<int, int, int>> *adj, int n, int m, ofstream &out) {

    bool cycle = false;

    vector<int> dist(n + 1, INF);
    dist[src] = 0;

    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[get<0>(neighbour)] > dist[node] + get<1>(neighbour)) {
                dist[get<0>(neighbour)] = dist[node] + get<1>(neighbour);
                bellman_ford.push(get<0>(neighbour));
                ++get<2>(neighbour);
                if (get<2>(neighbour) == 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() {
    ifstream in("bellmanford.in");
    ofstream out("bellmanford.out");

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

    vector<tuple<int, 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(make_tuple(v, weight, 0));
    }

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

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