Вы являетесь мэром Берлятова. Всего в городе \(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)\) после оптимального применения операции, описанной выше.
Выходные данные
Выведите одно целое число — минимальную суммарную стоимость курьерских маршрутов, которой вы можете достичь (то есть минимальное значение \(\sum\limits_{i=1}^{k} d(a_i, b_i)\), где \(d(x, y)\) равно стоимости самого дешевого пути между районами \(x\) и \(y\)), если вы можете сделать стоимость какой-то (не более, чем одной) дороги равной нулю.
Примечание
Картинка, соответствующая первому примеру:
Здесь вы можете выбрать либо дорогу \((2, 4)\), либо дорогу \((4, 6)\). Оба варианта приведут к суммарной стоимости \(22\).
Картинка, соответствующая второму примеру:
Здесь вы можете выбрать дорогу \((3, 4)\). Это приведет к суммарной стоимости \(13\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6 5 2
1 2 5
2 3 7
2 4 4
4 5 2
4 6 8
1 6
5 3
|
22
|
|
2
|
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
|