An adventurer is exploring a mysterious dungeon consisting of N rooms, numbered from 0 to N-1. The rooms are connected by `E` one-way passages.
Each passage has an integer energy cost. A positive value represents energy consumption, while a negative value represents energy recovery from magical effects.
The adventurer starts in room S and wants to reach room T with the minimum total energy cost.
Your task is to write a C/C++ program to determine the minimum total energy cost from room S to room T.
The dungeon follows these rules:
1. Each passage connects two different rooms and can only be traveled in the specified direction.
2. Passage weights may be positive, zero, or negative.
3. Multiple paths may exist between the starting room and the destination room.
4. If a finite shortest path exists from S to T, it is guaranteed to be unique.
5. Negative-weight cycles may exist in the dungeon.
6. Some rooms may be unreachable from the starting room.
Your program MAY use C/C++ standard library headers.
The first line contains an integer M, representing the number of dungeons.
For each dungeon:
The first line contains four integers N, E, S, and T, representing the number of rooms, the number of directed passages, the starting room, and the destination room.
The following E lines each contain three integers u, v, and w, indicating a directed passage from room u to room v with energy cost w.
There are no self-loops or duplicate directed edges.
1 <= M <= 10
2 <= N <= 3000
0 <= E <= 6000
0 <= S, T < N
S != T
0 <= u, v < N
u != v
-1000 <= w <= 1000
The sum of N over all dungeons does not exceed 10000.
The sum of E over all dungeons does not exceed 20000.
For each dungeon, output exactly one line according to the following conditions:
- If room T is unreachable from room S, output INF.
- If a negative-weight cycle is reachable from S and can reach T, output `NEGATIVE CYCLE`.
- Otherwise, output the minimum total energy cost from S to T.