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

using namespace std;

#define INF (INT32_MAX)

struct Edge {
    int src, dst, cost;

    Edge() : src(0), dst(0), cost(0) {}
    Edge(int src, int dst, int cost) :
        src(src), dst(dst), cost(cost) {}
};

/**
 * graph = o lista cu toate muchiile grafului
 */
vector<int> BellmanFord(int srcNode, int nrNodes, vector<Edge> &graph, bool &cycle)
{
    // STEP 0: initializarea
    vector<int> dist(nrNodes, INF);
    vector<int> parent(nrNodes, -1);

    // STEP 1: setarea nodurului sursa
    dist[srcNode] = 0;
    parent[srcNode] = 0;

    // STEP 2: executa (nrNodes - 1) relaxari, pentru fiecare muchie din graf
    for (int i = 1; i <= nrNodes - 1; i++) {
        for (Edge &edge : graph) {
            int node = edge.src;
            int neigh = edge.dst;
            int weight = edge.cost;

            if (dist[node] + weight < dist[neigh]) {
                dist[neigh] = dist[node] + weight;
                parent[neigh] = node;
            }
        }
    }


    // STEP 3:  verifica daca muchiile mai pot fi relaxate
    cycle = false;
    for (Edge &edge : graph) {
        int node = edge.src;
        int neigh = edge.dst;
        int weight = edge.cost;
    
        if (dist[node] + weight < dist[neigh]) {
            // a fost detectat un ciclu
            cout << "Ciclu negativ!\n";
            cycle = true;

            // intoarce un vector fara elemente
            return vector<int>(); 
        }
    }




    return dist;
}




void citireFisier(int &nrNodes, int &nrEdges, vector<Edge> &graph)
{
    ifstream fin("bellmanford.in");

    if (!fin) {
        cerr << "Error at opening file `bellmanford.in`";
        exit(EXIT_FAILURE);
    }

    fin >> nrNodes >> nrEdges;

    graph.resize(nrNodes);

    int src = 0, dst = 0, cost = 0;

    while (fin >> src >> dst >> cost)
        graph.push_back(Edge(src - 1, dst - 1, cost));
}




void scriereFisier(bool cycle, vector<int> &dist)
{
    ofstream fout("bellmanford.out");

    if (cycle == true) {
        fout << "Ciclu negativ!\n";
        fout.close();
        return;
    }

    for (int i = 1; i < dist.size(); i++)
        fout << dist[i] << " ";
    fout << "\n";
    fout.close();
}



int main()
{
    int nrNodes = 0, nrEdges = 0;
    vector<Edge> graph;

    citireFisier(nrNodes, nrEdges, graph);


    bool cycle;

    vector<int> dist = BellmanFord(0, nrNodes, graph, cycle);


    scriereFisier(cycle, dist);


    return 0;
}