No_Idea

#include <iostream>
#include <vector>
#include <bitset>
#include <queue>
using namespace std;

#define INF 0x7fffffff
#define x first
#define y second

vector<int> dijkstra(const vector<vector<pair<int, int>>> &Edges, const unsigned int N){
    /*
        Using an modification of dijkstra's algorithm.

        This algorithm can have Edges with negative values.
        This algorithm is posible to check whether there is any negative cicle or not.
    */
    pair< int, pair < int, bitset< N > > > aux;
    priority_queue< pair< int, pair< int, bitset< N > > > > Heap;
    int Weight[N], Last_Inside[N], Inside_Now = 0;
    bitset< N > &bitaux;

    for (int i = 0; i < N; i++){
        Last_Inside[i] = 0;
        Weight[i] = INF;
    }

    Heap.push(make_pair(0, make_pair(0, bitset< N >())));
    while (!Heap.empty()){
        aux = Heap.top();
        aux.x *= -1; // Using NegaMax idea
        Heap.pop();

        //check if it is smaller, instead of checked if it is visited
        if (Weight[aux.y.x] <= aux.x)
            continue;

        //check if the border expands
        if (Weight[aux.y.x] == INF)
            Inside_Now++;

        Weight[aux.y.x] = aux.x;

        for (unsigned int i = 0; i < Edges[aux.y.x].size(); i++)
            if (Edges[aux.y.x][i].y + aux.x < Weight[Edges[aux.y.x][i].x]){
                bitaux = aux.y.y;
                if(bitaux[Edges[aux.y.x].x]){
                    cout << "Negative Cicle";
                    return vector<int>(Weight, Weight + N);
                }
                bitaux[Edges[aux.y.x].x] = true;
                Heap.push(make_pair(-(Edges[aux.y.x][i].y + aux.x), make_pair(Edges[aux.y.x][i].x, bitaux)));
                bitaux[Edges[aux.y.x].x] = false;
            }

    }
    return vector<int>(Weight, Weight + N);
}

int main(){
    ios::sync_with_stdio(false); cin.tie(0);

    int N, M, from, to, w;
    cin >> N >> M;

    vector<vector<pair<int, int>>> Edges(N);
    vector<int> temp;

    for (int i = 0; i < M; i++){
        cin >> from >> to >> w;
        Edges[from].push_back(make_pair(to, w));
    }

    temp = dijkstra(Edges, N);

    cout << endl;
    for (int i = 0; i < N; i++)
        if (temp[i] != INF)
            cout << i << ": " << temp[i] << '\n';
        else
            cout << i << ": Don't pass here\n";

    return 0;
}