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

using namespace std;
using PII = pair<int, int>;

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

static constexpr int nMAX = ((int)(5e4) + 1), INF = ((int)(1e9));

int n;
vector<PII> G[nMAX];

void add_edge(const int x, const int y, const int c)
{
    G[x].push_back({c, y});
    return;
}

void load_graph()
{
    int m = 0;
    f >> n >> m;

    int x = 0, y = 0, c = 0;

    for (int i = 1; i <= m; ++i)
    {
        f >> x >> y >> c;
        add_edge(x, y, c);
    }

    return;
}

char analyze(const int i, const int n)
{
    if (i != n)
        return ' ';
    return '\n';
}

int main()
{
    load_graph();

    vector<int> d((n + 1), INF);
    vector<bool> in_queue((n + 1), false);
    vector<int> counts((n + 1), 0);

    queue<int> Q = {};

    d[1] = 0, in_queue[1] = true, counts[1] = 1;
    Q.push(1);

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

        in_queue[node] = false;

        for (const PII &e : G[node])
            if (d[node] + e.first < d[e.second])
            {
                d[e.second] = d[node] + e.first;

                if (in_queue[e.second])
                    continue;

                ++counts[e.second];
                if (counts[e.second] >= n)
                {
                    g << "Ciclu negativ!\n";
                    return 0;
                }

                in_queue[e.second] = true, Q.push(e.second);
            }
    }

    for (int i = 2; i <= n; ++i)
        g << d[i] << analyze(i, n);

    return 0;
}