#include <iostream>
#include <vector>
#include <climits>
#include <fstream>

using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
struct Edge
{
    int u, v, cost;
};

void bellmanFord(int n, int m, vector<Edge> &edges)
{
    vector<long long> dist(n + 1, LLONG_MAX); // Distantele minime
    dist[1] = 0;                              // Pornim din nodul 1

    // Relaxam toate muchiile de N-1 ori
    for (int i = 1; i <= n - 1; ++i)
    {
        for (const auto &edge : edges)
        {
            if (dist[edge.u] != LLONG_MAX && dist[edge.u] + edge.cost < dist[edge.v])
            {
                dist[edge.v] = dist[edge.u] + edge.cost;
            }
        }
    }

    // Detectam cicluri negative
    for (const auto &edge : edges)
    {
        if (dist[edge.u] != LLONG_MAX && dist[edge.u] + edge.cost < dist[edge.v])
        {
            fout << "Ciclu negativ!\n";
            return;
        }
    }

    // Afisam rezultatele
    for (int i = 2; i <= n; ++i)
    {
        if (dist[i] == LLONG_MAX)
        {
            fout << "INF ";
        }
        else
        {
            fout << dist[i] << " ";
        }
    }
    cout << "\n";
}

int main()
{
    int n, m;
    fin >> n >> m;

    vector<Edge> edges(m);
    for (int i = 0; i < m; ++i)
    {
        fin >> edges[i].u >> edges[i].v >> edges[i].cost;
    }

    bellmanFord(n, m, edges);

    return 0;
}