Некоторая лаборатория состоит из $$$n$$$ комнат, соединённых $$$m$$$ двусторонними коридорами, для прохождения которых требуется некоторое количество времени. В лаборатории проводились загадочные эксперименты со временем, в результате чего оказалось, что если пройти по некоторому маршруту и посетить при этом какие-то пары коридоров, потраченное время увеличится на некоторую величину, хотя на первый взгляд этого не должно происходить. Главный учёный узнал об этом, и поэтому собирается отправиться в основную комнату лаборатории $$$n$$$, чтобы исправить аномалии. Изначально он находится в комнате $$$1$$$.
Помогите ему определить, какое наименьшее время ему для этого понадобится. Если добраться до комнаты $$$n$$$ из комнаты $$$1$$$ невозможно, выведите $$$-1$$$.
В первой строке содержатся 3 целых числа $$$n, m$$$ и $$$k\, (1 \le n \le 10^5,\, 1 \le m \le 10^5,\, 0 \le k \le 5)$$$ – количество комнат в лаборатории, количество коридоров и количество пар особых коридоров.
В следующих $$$m$$$ строках содержатся по 3 числа $$$u, v$$$ и $$$t$$$, означающие, что между комнатами $$$u$$$ и $$$v$$$ есть двусторонний проход, на прохождение которого требуется $$$t$$$ времени $$$(1 \le u,v \le n,\, 1 \le t \le 10^9)$$$.
Далее в $$$k$$$ строках содержатся по 3 числа $$$i,\, j$$$ и $$$t\, (1 \le i,j \le m,\, i \ne j,\, 1 \le t \le 10^9)$$$, означающие, что если на пути от $$$1$$$ до $$$n$$$ учёный посетит и коридор номер $$$i$$$, и коридор номер $$$j$$$ (в любом порядке), то время его пути увеличится на $$$t$$$.
Гарантируется, что все номера $$$2 \cdot k$$$ коридоров, увеличивающих время, различны.
В единственной строке выведите ответ на задачу.
5 6 21 2 22 3 63 5 32 5 71 4 54 5 15 6 101 3 10
9
5 6 31 2 22 3 63 5 32 5 71 4 54 5 15 6 141 4 1002 3 10
20
| Весенний кубок МИФИ 2025 |
|---|
| Закончено |
