#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

const int INF = 2000000000;

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

// Structura pentru lista de adiacență: {vecin, cost}
struct Neighbor {
    int to;
    int cost;
};

// Funcția optimizată (SPFA)
// Returnează TRUE dacă există ciclu negativ, FALSE altfel
bool BellmanFord_SPFA(int startNode, int N, const vector<vector<Neighbor>>& adj, vector<int>& dist) {
    // 1. Inițializări
    dist.assign(N + 1, INF);
    vector<int> cnt(N + 1, 0);      // Numără de câte ori a fost un nod în coadă
    vector<bool> inQueue(N + 1, false); // Optimizare: să nu punem același nod de 2 ori în coadă
    queue<int> q;

    // Setăm startul
    dist[startNode] = 0;
    q.push(startNode);
    inQueue[startNode] = true;

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        inQueue[u] = false; // Nodul iese din coadă

        // Parcurgem doar vecinii nodului u (mult mai rapid decât să parcurgem toate muchiile)
        for (const auto& edge : adj[u]) {
            int v = edge.to;
            int c = edge.cost;

            // Relaxare
            if (dist[u] != INF && dist[u] + c < dist[v]) {
                dist[v] = dist[u] + c;

                // Dacă v nu e deja în coadă, îl adăugăm
                if (!inQueue[v]) {
                    q.push(v);
                    inQueue[v] = true;
                    cnt[v]++;

                    // Verificare Ciclu Negativ
                    // Dacă un nod e actualizat de mai mult de N ori, e prins într-un ciclu infinit
                    if (cnt[v] >= N) {
                        return true; // Ciclu negativ detectat
                    }
                }
            }
        }
    }

    return false; // Totul e OK
}

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

    // Folosim Listă de Adiacență (vector de vectori) pentru viteză
    vector<vector<Neighbor>> adj(N + 1);

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

    vector<int> dist;

    // Apelăm funcția optimizată
    bool hasNegativeCycle = BellmanFord_SPFA(1, N, adj, dist);

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

    return 0;
}