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

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

struct arc
{
    int destination;
    int weight;
};

const int INF = 2147483647;

int n, m;

bool negativeWeightCycle;

std :: vector < int > distance;

std :: vector < bool > inQueue;

std :: vector < std::vector < arc > > neighbours;

std :: queue < int > q1, q2;

void BellmanFord(int source, bool &negativeWeightCycle)
{
    for (int i=1; i<=n; i++)
        distance[i] = INF;

    distance[source] = 0;
    q1.push(source);

    for (int i=1; i<n; i++)
    {
        while (!q1.empty())
        {
            int node = q1.front();
            q1.pop();

            for (auto it : neighbours[node])
                if (distance[node] + it.weight < distance[it.destination])
                {
                    distance[it.destination] = distance[node] + it.weight;
                    if (!inQueue[it.destination])
                    {
                        inQueue[it.destination] = true;
                        q2.push(it.destination);
                    }
                }
        }

        if (q2.empty())
            return;

        while (!q2.empty())
        {
            q1.push(q2.front());
            inQueue[q2.front()] = false;
            q2.pop();
        }
    }

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

            for (auto it : neighbours[node])
                if (distance[node] + it.weight < distance[it.destination])
                    negativeWeightCycle = true;
    }
}

int main()
{
    f >> n >> m;

    inQueue.resize(n + 1);
    distance.resize(n + 1);
    neighbours.resize(n + 1);

    for (int i=1; i<=m; i++)
    {
        int x, y, c; f >> x >> y >> c;
        neighbours[x].push_back({y, c});
    }

    BellmanFord(1, negativeWeightCycle);

    if (negativeWeightCycle)
        g << "Ciclu negativ!";
    else
    {
        for (int i=2; i<=n; i++)
            g << distance[i] << " ";
    }

    return 0;
}