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

using namespace std;

struct Node
{
    int cost;
    vector<pair<int, int>> edges;
};

using Graph = vector<Node>;

const int kInfinite = (1 << 30);

bool FindDistances(Graph &g, int start)
{
    queue<int> q;
    vector<unsigned> times_used(g.size(), 0);

    for (auto &node : g) {
        node.cost = kInfinite;
    }

    q.push(start);
    g[start].cost = 0;

    while (!q.empty()) {
        int node = q.front();
        q.pop();

        ++times_used[node];
        if (times_used[node] >= g.size()) {
            return false;
        }

        for (const auto &edge : g[node].edges) {
            int new_cost = g[node].cost + edge.second;
            int neighbour = edge.first;
            if (g[neighbour].cost > new_cost) {
                g[neighbour].cost = new_cost;
                q.push(neighbour);
            }
        }
    }
    return true;
}

int main()
{
    ifstream fin("bellmanford.in");
    ofstream fout("bellmanford.out");

    int n, m;
    fin >> n >> m;

    Graph graph(n);
    while (m--) {
        int x, y, c;
        fin >> x >> y >> c;
        graph[x - 1].edges.push_back({y - 1, c});
    }

    bool correct = FindDistances(graph, 0);
    if (!correct) {
        fout << "Ciclu negativ!\n";
    } else {
        for (int i = 1; i < n; ++i) {
            fout << graph[i].cost << " ";
        }
        fout << "\n";
    }

    return 0;
}