Pomagasz w przebudowie centrum danych, aby zrobić miejsce na więcej procesorów graficznych (GPU). Przez lata centrum danych stało się zagracone zbędnym okablowaniem sieciowym, a Ty zostałeś poproszony o posprzątanie tego bałaganu i odzyskanie jak największej ilości nieużywanych kabli.

Rysunek C.1: Ilustracja przykładowego wejścia 1. Serwery w tej samej sparowanej parze mają ten sam kolor. Kable do usunięcia zaznaczono linią przerywaną.

Centrum danych posiada $N$ serwerów i $N$ kabli sieciowych, które łączą jeden serwer z drugim. Każdy kabel ma określoną długość w stopach. Ruch przepływa przez kable sieciowe w obu kierunkach, a centrum danych jest początkowo połączone: dla każdej pary serwerów $(u, v)$ istnieje ścieżka kabli sieciowych z $u$ do $v$ (prawdopodobnie przechodząca przez serwery pośrednie). Przeprowadziłeś audyt ruchu sieciowego w centrum danych i odkryłeś, że tylko $K$ sparowanych par serwerów musi się ze sobą komunikować. (Zauważ, że niektóre serwery mogą nie być częścią żadnej sparowanej pary lub mogą być częścią dwóch lub więcej sparowanych par).

Musisz teraz usunąć jak największą łączną długość kabli z centrum danych, zachowując jednocześnie połączenie między wszystkimi sparowanymi parami: dla każdej takiej pary serwerów $(a, b)$ musi istnieć ścieżka z $a$ do $b$ przechodząca przez oryginalne kable sieciowe, które pozostawiłeś na miejscu.

Znajdź minimalną łączną długość kabla, która musi pozostać na miejscu, aby spełnić ten warunek.

Wejście

Pierwsza linia wejścia zawiera dwie liczby całkowite oddzielone spacją $N$ ($3 \le N \le 10^5$) oraz $K$ ($1 \le K \le 10^5$), oznaczające liczbę serwerów w centrum danych oraz liczbę odkrytych sparowanych par serwerów.

Kolejne $N$ linii opisuje kable sieciowe znajdujące się pierwotnie w centrum danych. Każda linia zawiera trzy liczby całkowite oddzielone spacją $u_i, v_i$ ($1 \le u_i, v_i \le N, u_i \neq v_i$) oraz $w_i$ ($1 \le w_i \le 10^9$), określające, że kabel łączy serwer $u_i$ z serwerem $v_i$ i ma długość $w_i$ stóp. Istnieje co najwyżej jeden kabel sieciowy łączący parę serwerów, a graf serwerów i kabli jest spójny.

Każda z kolejnych $K$ linii zawiera dwie liczby całkowite oddzielone spacją $a_j$ oraz $b_j$ ($1 \le a_j, b_j \le N, a_j \neq b_j$) i opisuje sparowaną parę serwerów. Każda sparowana para musi pozostać połączona ścieżką po zakończeniu usuwania kabli. Wszystkie sparowane pary są różne; $(a, b)$ oraz $(b, a)$ są uważane za tę samą parę i nie zostaną wymienione dwukrotnie jako sparowane pary.

Wyjście

Wypisz pojedynczą liczbę całkowitą: minimalną łączną długość kabla sieciowego (w stopach), która musi pozostać na miejscu, aby wszystkie $K$ sparowanych par serwerów pozostały ze sobą połączone.

Przykład 1

Wejście 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

Wyjście 1

57

Przykład 2

Wejście 2

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

Wyjście 2

9