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

#define INFINIT INT_MAX

using namespace std;

class Graf {
private:
    int nrNoduri, nrMuchii;
    vector<pair<int, pair<int, int>>> muchii; // Lista de muchii {cost, {sursa, destinatie}}

public:
    Graf(int nrNoduri, int nrMuchii);
    void adaugaMuchie(int sursa, int destinatie, int cost);
    void rezolvaBellmanFord(int nodStart);
};

Graf::Graf(int nrNoduri, int nrMuchii) {
    this->nrNoduri = nrNoduri;
    this->nrMuchii = nrMuchii;
}

// Adaugă o muchie între două noduri
void Graf::adaugaMuchie(int sursa, int destinatie, int cost) {
    muchii.push_back({cost, {sursa, destinatie}});
}

// Implementarea algoritmului Bellman-Ford
void Graf::rezolvaBellmanFord(int nodStart) {
    vector<int> distanta(nrNoduri + 1, INFINIT); // Inițial, toate distanțele sunt infinit
    distanta[nodStart] = 0; // Distanța până la nodul de start este 0

    // Relaxez toate muchiile (nrNoduri - 1) ori
    for (int i = 1; i <= nrNoduri - 1; i++) {
        for (auto &muchie : muchii) {
            int cost = muchie.first;
            int sursa = muchie.second.first;
            int destinatie = muchie.second.second;

            if (distanta[sursa] != INFINIT && distanta[sursa] + cost < distanta[destinatie]) {
                distanta[destinatie] = distanta[sursa] + cost;
            }
        }
    }

    // Verific ciclurile negative
    for (auto &muchie : muchii) {
        int cost = muchie.first;
        int sursa = muchie.second.first;
        int destinatie = muchie.second.second;

        if (distanta[sursa] != INFINIT && distanta[sursa] + cost < distanta[destinatie]) {
            cout << "Ciclu negativ!" << endl;
            return;
        }
    }

    // Afișez distanțele
    for (int i = 1; i <= nrNoduri; i++) {
        if (distanta[i] == INFINIT)
            cout << "INF ";
        else
            cout << distanta[i] << " ";
    }
    cout << endl;
}

int main() {
    int nrNoduri, nrMuchii;
    cin >> nrNoduri >> nrMuchii;

    Graf g(nrNoduri, nrMuchii);

    for (int i = 0; i < nrMuchii; i++) {
        int sursa, destinatie, cost;
        cin >> sursa >> destinatie >> cost;
        g.adaugaMuchie(sursa, destinatie, cost);
    }

    int nodStart = 1; // Nodul de start
    g.rezolvaBellmanFord(nodStart);

    return 0;
}