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

using namespace std;

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

vector<int> distanta(50005, numeric_limits<int>::max());
vector<int> inQueueCount(50005, 0);

bool Bellman_Ford(int source, int noNodes, vector<vector<pair<int, int>>> &graph)
{
    queue<int> Q;
    vector<bool> inQueue(noNodes + 1, false);

    distanta[source] = 0;
    Q.push(source);
    inQueue[source] = true;

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

        for (auto &neighbor : graph[node])
        {
            int weight = neighbor.first;
            int newNode = neighbor.second;

            if (distanta[node] != numeric_limits<int>::max() && distanta[node] + weight < distanta[newNode])
            {
                distanta[newNode] = distanta[node] + weight;

                if (!inQueue[newNode])
                {
                    Q.push(newNode);
                    inQueue[newNode] = true;
                    inQueueCount[newNode]++;

                    // If a node is added to the queue more than "noNodes" times, there's a negative cycle.
                    if (inQueueCount[newNode] > noNodes)
                    {
                        return false;
                    }
                }
            }
        }
    }

    // Output distances for nodes 2 to noNodes.
    for (int i = 2; i <= noNodes; i++)
    {
        if (distanta[i] == numeric_limits<int>::max())
        {
            fout << "INF ";
        }
        else
        {
            fout << distanta[i] << " ";
        }
    }

    return true;
}

int main()
{
    int noNodes, noEdges;
    fin >> noNodes >> noEdges;

    vector<vector<pair<int, int>>> graph(noNodes + 1);

    for (int i = 1; i <= noEdges; i++)
    {
        int firstNode, secondNode, weight;
        fin >> firstNode >> secondNode >> weight;

        graph[firstNode].emplace_back(weight, secondNode);
    }

    if (!Bellman_Ford(1, noNodes, graph))
    {
        fout << "Ciclu negativ!";
    }

    return 0;
}