#include <fstream>
#include <vector>

using namespace std;

const int INF = 2000000000;

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

struct Muchie {
    int u, v, cost;
};

int main() {
    int N, M;
    fin >> N >> M;

    vector<Muchie> muchii;
    // Prealocăm memoria pentru viteză puțin mai mare
    muchii.reserve(M); 

    for (int i = 0; i < M; i++) {
        int u, v, c;
        fin >> u >> v >> c;
        muchii.push_back({u, v, c});
    }

    // 1. Inițializare
    vector<int> dist(N + 1, INF);
    dist[1] = 0;

    // 2. Relaxare (Algoritmul Clasic)
    // Repetăm de N-1 ori
    bool ciclu_negativ = false;
    
    for (int i = 1; i <= N; i++) { 
        bool modificat = false;
        
        for (const auto& m : muchii) {
            if (dist[m.u] != INF && dist[m.u] + m.cost < dist[m.v]) {
                // Dacă suntem la pasul N (adică i == N) și încă relaxăm -> Ciclu negativ
                if (i == N) {
                    ciclu_negativ = true;
                }
                
                dist[m.v] = dist[m.u] + m.cost;
                modificat = true;
            }
        }

        // Optimizare: Dacă nu s-a modificat nimic într-o trecere completă, ne oprim.
        // Asta e singura șansă să iei puncte pe teste medii.
        if (!modificat) break;
    }

    if (ciclu_negativ) {
        fout << "ciclu negativ!";
    } else {
        for (int i = 2; i <= N; i++) {
            fout << dist[i] << " ";
        }
    }

    return 0;
}