#include <bits/stdc++.h>

using namespace std;

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

int N, M;

struct Edge
{
    int x, y, cost;
};

vector<Edge> edges;

void Citire()
{
    fin >> N >> M;
    while (M--)
    {
        int x, y, cost;
        fin >> x >> y >> cost;
        edges.push_back( { x, y, cost } );
    }
}

constexpr int oo = 2000000005;
vector<int> dp;

void Bellman_Ford()
{
    dp.assign(N + 1, oo);
    dp[1] = 0;

    for (int i = 1; i < N; i++)
        for (auto e : edges)
        {
            if (dp[e.x] >= oo) continue;
            if (dp[e.y] > dp[e.x] + e.cost)
                dp[e.y] = dp[e.x] + e.cost;
        }

    for (auto e : edges)
    {
        if (dp[e.x] >= oo) continue;
        if (dp[e.y] > dp[e.x] + e.cost)
        {
            fout << "Ciclu negativ!\n";
            return;
        }
    }

    for (int i = 2; i <= N; i++)
        fout << dp[i] << ' ';
    fout << '\n';
}

int main()
{
    Citire();
    Bellman_Ford();

    fin.close();
    fout.close();
    return 0;
}