Đường ngắn nhất dưới ảnh hưởng chu trình âm

Bối cảnh và bài toán

Một mạng có cạnh âm. Ta chỉ quan tâm đường từ s tới t. Nếu có chu trình âm đi được từ s và từ chu trình đó vẫn tới t, bài toán không có giá trị hữu hạn.

Yêu cầu

In NEGATIVE nếu đáp án có thể giảm vô hạn; ngược lại in khoảng cách ngắn nhất, hoặc UNREACHABLE nếu t không tới được.

Input

Dòng đầu n, m, s, t; tiếp theo m cạnh có hướng u, v, w.

Output

In "NEGATIVE", "UNREACHABLE" hoặc một số nguyên.

Ràng buộc

• 1 <= n <= 2500
• 0 <= m <= 5000
• -10^9 <= w <= 10^9 ## Chấm điểm | Subtask | Điểm | Điều kiện | Official tests | |---|---:|---|---| | S1 | 40 | n <= 100, m <= 300 | 01–08 | | S2 | 60 | Không có ràng buộc bổ sung | 09–20 |

Ví dụ 1

Input

4 4 1 4
1 2 1
2 3 -3
3 2 1
3 4 2

Output

NEGATIVE

Giải thích. Chỉ chu trình âm vừa reachable từ s vừa có thể dẫn tới t mới khiến đáp án giảm vô hạn.

Ví dụ 2

Input

4 2 1 4
1 2 5
2 3 1

Output

UNREACHABLE

Giải thích. Chỉ chu trình âm vừa reachable từ s vừa có thể dẫn tới t mới khiến đáp án giảm vô hạn.

Thông tin bài tập

Nguồn: FULLHOUSE DEV – Self-generated.