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

#define INFINIT INT_MAX

using namespace std;

class Graf {
private:
    int nrNoduri; // Numărul de noduri
    vector<pair<int, int>> *adiacenta; // Lista de adiacență ponderată: {destinatie, cost}

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

// Constructor pentru a inițializa graful
Graf::Graf(int nrNoduri) {
    this->nrNoduri = nrNoduri;
    adiacenta = new vector<pair<int, int>>[nrNoduri + 1]; // Creez lista de adiacență
}

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

// 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 (int nod = 1; nod <= nrNoduri; nod++) {
            for (auto vecin : adiacenta[nod]) {
                int destinatie = vecin.first;
                int cost = vecin.second;

                // Dacă se poate îmbunătăți distanța până la vecin, actualizez
                if (distanta[nod] != INFINIT && distanta[nod] + cost < distanta[destinatie]) {
                    distanta[destinatie] = distanta[nod] + cost;
                }
            }
        }
    }

    // Verific dacă există cicluri de cost negativ
    for (int nod = 1; nod <= nrNoduri; nod++) {
        for (auto vecin : adiacenta[nod]) {
            int destinatie = vecin.first;
            int cost = vecin.second;

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

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

// Destructor pentru a elibera memoria
Graf::~Graf() {
    delete[] adiacenta;
}

// Funcția principală pentru testarea algoritmului Bellman-Ford
int main() {
    int nrNoduri, nrMuchii;
    cin >> nrNoduri >> nrMuchii;

    Graf g(nrNoduri);

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

    int nodStart = 1; // Pornesc de la nodul 1 (sau altul, după cerință)
    g.rezolvaBellmanFord(nodStart);

    return 0;
}