G. Уменьшение стоимости доставки
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вы являетесь мэром Берлятова. Всего в городе $$$n$$$ районов и $$$m$$$ двусторонних дорог между ними. $$$i$$$-я дорога соединяет районы с индексами $$$x_i$$$ и $$$y_i$$$. Стоимость путешествия по этой дороге равна $$$w_i$$$. Между каждой парой районов существует какой-то путь, поэтому город является связным.

Всего в Берлятове есть $$$k$$$ курьерских маршрутов. $$$i$$$-й маршрут идет из района $$$a_i$$$ в район $$$b_i$$$. На каждом маршруте находится один курьер и он всегда будет выбирать самый дешевый (минимальный по суммарной стоимости) путь из района $$$a_i$$$ в район $$$b_i$$$ для доставки продуктов.

Маршрут может идти из района в него же, также некоторые курьерские маршруты могут совпадать (и вам необходимо учитывать их независимо).

Вы можете уменьшить стоимость не более чем одной дороги до нуля (то есть вы выбираете не более одной дороги и заменяете ее стоимость на $$$0$$$).

Пусть $$$d(x, y)$$$ равно самой дешевой стоимости путешествия между районами $$$x$$$ и $$$y$$$.

Ваша задача — найти минимальную суммарную стоимость курьерских маршрутов, которую вы можете достичь, если вы оптимально выберете какую-то дорогу и замените ее стоимость на $$$0$$$. Другими словами, вам необходимо найти минимально возможное значение $$$\sum\limits_{i = 1}^{k} d(a_i, b_i)$$$ после оптимального применения операции, описанной выше.

Входные данные

Первая строка входных данных содержит три целых числа $$$n$$$, $$$m$$$ and $$$k$$$ ($$$2 \le n \le 1000$$$; $$$n - 1 \le m \le min(1000, \frac{n(n-1)}{2})$$$; $$$1 \le k \le 1000$$$) — количество районов, количество дорог и количество курьерских маршрутов.

Следующие $$$m$$$ строк описывают дороги. $$$i$$$-я дорога задана тремя целыми числами $$$x_i$$$, $$$y_i$$$ и $$$w_i$$$ ($$$1 \le x_i, y_i \le n$$$; $$$x_i \ne y_i$$$; $$$1 \le w_i \le 1000$$$), где $$$x_i$$$ и $$$y_i$$$ — районы, которые соединены $$$i$$$-й дорогой, а $$$w_i$$$ — ее стоимость. Гарантируется, что между каждой парой районов существует какой-то путь, поэтому город является связным. Также гарантируется, что между каждой парой районов существует не более одной дороги.

Следующие $$$k$$$ строк описывают курьерские маршруты. $$$i$$$-й маршрут задан двумя целыми числами $$$a_i$$$ и $$$b_i$$$ ($$$1 \le a_i, b_i \le n$$$) — районами $$$i$$$-го маршрута. Маршрут может идти из района в него же, также некоторые курьерские маршруты могут совпадать (и вам необходимо учитывать их независимо).

Выходные данные

Выведите одно целое число — минимальную суммарную стоимость курьерских маршрутов, которой вы можете достичь (то есть минимальное значение $$$\sum\limits_{i=1}^{k} d(a_i, b_i)$$$, где $$$d(x, y)$$$ равно стоимости самого дешевого пути между районами $$$x$$$ и $$$y$$$), если вы можете сделать стоимость какой-то (не более, чем одной) дороги равной нулю.

Примеры
Входные данные
6 5 2
1 2 5
2 3 7
2 4 4
4 5 2
4 6 8
1 6
5 3
Выходные данные
22
Входные данные
5 5 4
1 2 5
2 3 4
1 4 3
4 3 7
3 5 2
1 5
1 3
3 3
1 5
Выходные данные
13
Примечание

Картинка, соответствующая первому примеру:

Здесь вы можете выбрать либо дорогу $$$(2, 4)$$$, либо дорогу $$$(4, 6)$$$. Оба варианта приведут к суммарной стоимости $$$22$$$.

Картинка, соответствующая второму примеру:

Здесь вы можете выбрать дорогу $$$(3, 4)$$$. Это приведет к суммарной стоимости $$$13$$$.