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

using namespace std;

struct Edge {
    int source, target, weight;
};

void BellmanFord(int N, int M, vector<Edge>& edges, ofstream& outFile) {
    vector<int> distance(N, INT_MAX);
    distance[0] = 0; // Distanta de la nodul sursă (1) la el însuși este 0

    bool updated;
    for (int i = 0; i < N - 1; ++i) {
        updated = false;
        for (const Edge& e : edges) {
            if (distance[e.source] != INT_MAX && distance[e.source] + e.weight < distance[e.target]) {
                distance[e.target] = distance[e.source] + e.weight;
                updated = true;
            }
        }
        if (!updated) break; // Oprire timpurie dacă nu s-au făcut actualizări
    }

    // Verificăm pentru cicluri de cost negativ
    for (const Edge& e : edges) {
        if (distance[e.source] != INT_MAX && distance[e.source] + e.weight < distance[e.target]) {
            outFile << "Ciclu negativ!\n";
            return;
        }
    }

    // Scriem costurile minime în fișierul de ieșire
    for (int i = 1; i < N; ++i) {
        if (distance[i] == INT_MAX) {
            outFile << "Infinit ";
        } else {
            outFile << distance[i] << " ";
        }
    }
    outFile << "\n";
}

int main() {
    ifstream inFile("bellmanford.in");
    ofstream outFile("bellmanford.out");

    int N, M;
    inFile >> N >> M;

    vector<Edge> edges(M);
    for (int i = 0; i < M; ++i) {
        inFile >> edges[i].source >> edges[i].target >> edges[i].weight;
        edges[i].source--; // Adjusting for 0-based indexing
        edges[i].target--;
    }

    BellmanFord(N, M, edges, outFile);

    inFile.close();
    outFile.close();

    return 0;
}