#include <bits/stdc++.h>
#include <fstream>
using namespace std;

ifstream f("bellmanford.in");
ofstream g("bellmanford.out");

int main() {
    int n, m, i, x, y, c;
    f >> n >> m;
    vector<vector<pair<int, int>>> edges(n + 1);
    vector<int> d(n + 1, INT_MAX), cnt(n + 1, 0);
    vector<bool> inqueue(n + 1, false);
    for(i = 0; i < m; ++i) {
        f >> x >> y >> c;
        edges[x].push_back({y, c});
        // edges[y].push_back({x, c});
    }

    d[1] = 0;
    inqueue[1] = true;

    queue<int> q;
    q.push(1);

    while(!q.empty()) {
        int node = q.front();
        q.pop();
        inqueue[node] = false;

        for(auto& edge: edges[node]) {
            int dist = edge.second, to = edge.first;

            if(d[node] + dist < d[to]) {
                d[to] = d[node] + dist;

                if(!inqueue[to]) {
                    q.push(to);
                    inqueue[to] = true;

                    if(++cnt[to] > n) {
                        g << "Ciclu negativ!";
                        return 0;
                    }
                }
            }
        }
    }

    for(i = 2; i <= n; ++i)
        g << d[i] << ' ';

    return 0;
}