Estás ayudando a remodelar un centro de datos para hacer espacio para más GPUs. Con el paso de los años, el centro de datos se ha llenado de cables de red superfluos, y se te ha pedido que limpies el desorden y recuperes la mayor cantidad posible de cable no utilizado.

Figura C.1: Una ilustración de la Entrada de ejemplo 1. Los servidores en el mismo par acoplado tienen el mismo color. Los cables a eliminar se indican con una línea discontinua.

El centro de datos tiene $N$ servidores y $N$ cables de red que conectan un servidor con otro. Cada cable tiene una longitud en pies. El tráfico fluye a través de los cables de red en ambas direcciones y el centro de datos está inicialmente conectado: para cada par de servidores $(u, v)$ existe un camino de cables de red desde $u$ hasta $v$ (posiblemente pasando por servidores intermedios). Has auditado el tráfico de red del centro de datos y descubierto que solo $K$ pares acoplados de servidores necesitan comunicarse entre sí. (Nota: algunos servidores podrían no ser parte de ningún par acoplado, o podrían ser parte de dos o más pares acoplados).

Ahora necesitas eliminar la mayor longitud total de cable posible del centro de datos mientras mantienes todos los pares acoplados conectados entre sí: para cada par de servidores $(a, b)$ debe existir un camino desde $a$ hasta $b$ pasando por los cables de red originales que has mantenido en su lugar.

Encuentra la longitud total mínima de cable que debe mantenerse en su lugar para satisfacer esta restricción.

Entrada

La primera línea de la entrada contiene dos enteros separados por espacios $N$ ($3 \le N \le 10^5$) y $K$ ($1 \le K \le 10^5$), el número de servidores en el centro de datos y el número de pares acoplados de servidores que has descubierto.

Las siguientes $N$ líneas describen los cables de red originalmente en el centro de datos. Cada línea contiene tres enteros separados por espacios $u_i, v_i$ ($1 \le u_i, v_i \le N, u_i \neq v_i$), y $w_i$ ($1 \le w_i \le 10^9$), especificando que un cable conecta el servidor $u_i$ con el servidor $v_i$ y tiene una longitud de $w_i$ pies. Existe como máximo un cable de red conectando un par de servidores y el grafo de servidores y cables está conectado.

Cada una de las siguientes $K$ líneas contiene dos enteros separados por espacios $a_j$ y $b_j$ ($1 \le a_j, b_j \le N, a_j \neq b_j$) y describe un par acoplado de servidores. Cada par acoplado debe permanecer conectado por un camino después de que termines de eliminar cables. Todos los pares acoplados son distintos; $(a, b)$ y $(b, a)$ se consideran el mismo y no aparecerán ambos en la lista de pares acoplados.

Salida

Imprime un solo entero: la longitud total mínima de cable de red (en pies) que debe permanecer en su lugar para que todos los $K$ pares de servidores acoplados permanezcan conectados entre sí.

Ejemplos

Entrada 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

Salida 1

57

Entrada 2

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

Salida 2

9