#include <fstream>
#include <vector>
#include <bitset>
#include <queue>
#include <climits>

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

const int nMax = 5e4;

int main () {
    int n, m; fin >> n >> m;
    std::vector<std::vector<std::pair<int, int>>> graph(n);
    for (int i = 0; i < m; i += 1) {
        int a, b, c; fin >> a >> b >> c; a -= 1, b -= 1;
        graph[a].emplace_back (std::make_pair (b, c));
    }

    std::bitset<nMax> inqueue; inqueue[0] = 1;

    std::vector<int> dist(n, (int) 1e9), counter(n, 0); dist[0] = 0;

    std::priority_queue<std::pair<int, int>> heap; heap.push ({0, 0});

    while (!heap.empty ()) {
        int node = heap.top ().second;
        int distance = -heap.top ().first;
        heap.pop (); inqueue[node] = 0;

        for (auto & it : graph[node])
            if (dist[it.first] > dist[node] + it.second) {
                dist[it.first] = dist[node] + it.second;
                if (!inqueue[it.first]) {
                    inqueue[it.first] = 1;
                    heap.push ({-dist[it.first], it.first});

                    counter[it.first] += 1;
                    if (counter[it.first] > n) {
                        fout << "Ciclu negativ!";
                        return 0;
                    }
                }
            }
    }

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