Вы помогаете реконструировать центр обработки данных, чтобы освободить место для большего количества графических процессоров. За прошедшие годы центр обработки данных оказался загроможден лишними сетевыми кабелями, и вас попросили навести порядок и вернуть как можно больше неиспользуемых кабелей.

Рисунок C.1: Иллюстрация примера входных данных 1. Серверы в одной связанной паре отмечены одинаковым цветом. Кабели, подлежащие удалению, обозначены пунктирной линией.

В центре обработки данных есть $N$ серверов и $N$ сетевых кабелей, соединяющих серверы друг с другом. Каждый кабель имеет длину в футах. Трафик передается по сетевым кабелям в обоих направлениях, и изначально центр обработки данных связен: для любой пары серверов $(u, v)$ существует путь из сетевых кабелей от $u$ до $v$ (возможно, проходящий через промежуточные серверы). Вы проанализировали сетевой трафик центра обработки данных и обнаружили, что только $K$ пар серверов должны обмениваться данными друг с другом. (Заметьте, что некоторые серверы могут не входить ни в одну связанную пару, а некоторые могут входить в две или более пар.)

Теперь вам нужно удалить как можно большую суммарную длину кабелей из центра обработки данных, сохранив при этом связность всех пар серверов: для каждой такой пары серверов $(a, b)$ должен существовать путь от $a$ до $b$, проходящий через оставленные вами исходные сетевые кабели.

Найдите минимальную суммарную длину кабелей, которую необходимо оставить, чтобы удовлетворить этому ограничению.

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

Первая строка входных данных содержит два целых числа, разделенных пробелом: $N$ ($3 \le N \le 10^5$) и $K$ ($1 \le K \le 10^5$) — количество серверов в центре обработки данных и количество обнаруженных вами связанных пар серверов.

Следующие $N$ строк описывают сетевые кабели, изначально имеющиеся в центре обработки данных. Каждая строка содержит три целых числа, разделенных пробелом: $u_i, v_i$ ($1 \le u_i, v_i \le N, u_i \neq v_i$) и $w_i$ ($1 \le w_i \le 10^9$), указывающие, что кабель соединяет сервер $u_i$ с сервером $v_i$ и имеет длину $w_i$ футов. Между любой парой серверов существует не более одного сетевого кабеля, и граф серверов и кабелей является связным.

Каждая из следующих $K$ строк содержит два целых числа, разделенных пробелом: $a_j$ и $b_j$ ($1 \le a_j, b_j \le N, a_j \neq b_j$), описывающих связанную пару серверов. Каждая связанная пара должна оставаться соединенной путем после того, как вы закончите удаление кабелей. Все связанные пары различны; $(a, b)$ и $(b, a)$ считаются одной и той же парой и не будут оба указаны в списке связанных пар.

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

Выведите единственное целое число: минимальную суммарную длину сетевого кабеля (в футах), которую необходимо оставить, чтобы все $K$ пар серверов оставались соединенными друг с другом.

Примеры

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

8 3
5 3 5
1 7 20
3 8 8
7 5 15
5 2 12
1 6 9
5 1 10
7 4 7
3 4
8 2
1 7

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

57

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

5 1
1 3 3
4 2 4
3 4 2
5 2 2
4 1 6
2 1

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

9