#include <fstream>
using namespace std;

const int INF = 1000000000; // 1e9

struct Edge {
    int x, y, cost;
};

Edge edges[250001];
int dist[50001];

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

    int N, M;
    fin >> N >> M;

    for (int i = 1; i <= M; i++) {
        fin >> edges[i].x >> edges[i].y >> edges[i].cost;
    }

    // initializare distante
    for (int i = 1; i <= N; i++)
        dist[i] = INF;
    dist[1] = 0;

    // Bellman–Ford: N - 1 relaxari
    for (int i = 1; i <= N - 1; i++) {
        bool changed = false;

        for (int j = 1; j <= M; j++) {
            int x = edges[j].x;
            int y = edges[j].y;
            int c = edges[j].cost;

            if (dist[x] != INF && dist[x] + c < dist[y]) {
                dist[y] = dist[x] + c;
                changed = true;
            }
        }

        if (!changed) break; // optimizare
    }

    // verificare ciclu negativ
    for (int j = 1; j <= M; j++) {
        int x = edges[j].x;
        int y = edges[j].y;
        int c = edges[j].cost;

        if (dist[x] != INF && dist[x] + c < dist[y]) {
            fout << "Ciclu negativ!";
            return 0;
        }
    }

    // afisam distantele pentru nodurile 2..N
    for (int i = 2; i <= N; i++) {
        fout << dist[i];
        if (i < N) fout << " ";
    }

    return 0;
}