Условие

---

CODE@BURGAS 2026, ГРУПА B, ЗАДАЧА D. ПАРАДОКСАЛНО ПЪТУВАНЕ ВЪВ ВРЕМЕТО
---
Вие разполагате с машина на времето, но тя вече не работи по стандартен начин. Епохите са представени като върхове в ориентиран граф с n върха и m ребра. Всяко ребро има цена w и времева нестабилност t. 
Вашата цел е да намерите път от началния връх 1 до крайния връх n, като спазвате следните условия: 
- Не използвате повече от K нестабилни прехода (t > X) 
- Минимизирате сумарната цена 
- Не попадате в парадокс (отрицателен цикъл)

Ограничения: 
1 ≤ n ≤ 2000 
1 ≤ m ≤ 10000

Вход: 
На първият ред на стандартният вход са дадени n, m, K и X. Следват m реда с описание на ребрата: u v w t.

Изход: 
Ако съществува валиден път: 
STABLE TIME TRAVEL! 
<стойност> 
<дължина на пътя> 
<върхове> 
Ако има парадокс: 
TEMPORAL PARADOX! 
Ако няма възможен път: 
NO POSSIBLE TIMELINE!

Примерен вход 1:
6 11 1 4
3 4 8 14
6 3 -7 10
2 5 0 11
3 4 5 4
1 5 -5 16
2 5 6 0
4 5 3 11
1 5 9 9
2 6 -5 15
6 1 2 18
5 6 -10 4 	

Примерен изход 1:
STABLE TIME TRAVEL!
-15
3
1 5 6

Примерен вход 2:
5 12 3 7
2 4 -6 10
2 1 -1 15
4 3 5 14
4 2 -10 10
2 1 10 13
4 2 -2 12
2 1 -5 19
5 4 -1 17
3 2 -6 12
5 2 -7 14
2 1 7 17
3 5 -1 18	

Примерен изход 2
NO POSSIBLE TIMELINE!