#include <fstream>
#include <vector>
#include <climits>

std::ifstream fin("bellmanford.in");
std::ofstream fout("bellmanford.out");

struct Edge {
    int from, to, cost;
};

int main () {
    int n, m; fin >> n >> m;
    std::vector<Edge> edges(m);
    for (int i = 0; i < m; i += 1) {
        fin >> edges[i].from >> edges[i].to >> edges[i].cost;
        edges[i].from -= 1, edges[i].to -= 1;
    }


    std::vector<int> dist(n, (int) 1e9);

    dist[0] = 0;

    for (int i = 1; i < n; i += 1)
        for (int j = 0; j < m; j += 1)
            if (dist[edges[j].from] + edges[j].cost < dist[edges[j].to])
                dist[edges[j].to] = dist[edges[j].from] + edges[j].cost;

    for (int i = 0; i < m; i += 1)
        if (dist[edges[i].from] + edges[i].cost < dist[edges[i].to]) {
            fout << "Ciclu negativ!";
            return 0;
        }

    for (int i = 1; i < n; i += 1)
        fout << dist[i] << ' ';
    return 0;
}