/*

Enunt:
Să se determine dacă în graful dat există un ciclu de cost negativ.
Dacă nu există, să se determine costul minim al unui lanţ de la nodul 1 la fiecare dintre nodurile 2, 3, ... , N-1, N.

Implementare cu Bellman Ford;


Metoda 1 - Fara coada
Pasi:

!!! Fac N-1 repetari pt ca in cazul cel mai rau pot relaxa o singura muchie per nod.
La fiecare interatie:
     -> verific daca d[u] + w(u,v) < d[v]
     -> daca da inseamna ca pot updata costul in d[v] si pot pune tata[v] = u, fiind nodul din care venim cu cost minim



Tin evidenta nodurilor modificate intr-o coada. More efficent pt ca nu mai trebuie sa fac V-1 interatii.


*/

#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

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

//edge structure
struct Edge {
    int nod_x, nod_y, cost_edge;
};

const int INF = 1e9;

vector<Edge> edges;

//graph informations:
int N, M;
int tata[100000];
int d[100000];

int main() {
    int x, y , c;
    //read number of vertix and edges:
    fin >> N >> M;


    // compute edges list:
    for (int i = 1; i <= M; i++) {
        Edge e;
        fin >> e.nod_x >> e.nod_y >> e.cost_edge;
        edges.push_back(e);
    }

    //initializam vectorul de distante pentru fiecare nod si tata:
    for (int i = 1; i<= N; i++) {
        d[i] = INF;
        tata[i] = 0;
    }

    d[1] = 0;

    for (int i = 1; i<=N-1; i++) {

        // Relaxare: d[x] + w(x,y) < d[y]
        for (const Edge& e: edges) {
            if (d[e.nod_x]!= INF && d[e.nod_x] + e.cost_edge < d[e.nod_y]) {

                d[e.nod_y] = d[e.nod_x] + e.cost_edge;
                tata[e.nod_y] = e.nod_x;
            }
        }
    }

    bool ciclu_negativ = false;

    for (int i = 1; i<=N-1; i++) {

        // Relaxare la pas > N-1: d[x] + w(x,y) < d[y]
        for (const Edge e: edges) {
            if (d[e.nod_x] + e.cost_edge < d[e.nod_y]) {
                ciclu_negativ = true;
            }
        }
        if (ciclu_negativ == true){
            fout << "Ciclu Negativ";
            break;
        }
    }
    if (ciclu_negativ) {
        fout << "Ciclu negativ!";
    }
    else {
        for (int i = 2; i <= N; i++) {
            fout << d[i] << " ";
        }
    }
}