Vous aidez à réorganiser un centre de données pour faire de la place à davantage de GPU. Au fil des ans, le centre de données est devenu encombré de câbles réseau superflus, et on vous a demandé de nettoyer le désordre et de récupérer autant de câbles inutilisés que possible.

Figure C.1 : Une illustration de l'exemple d'entrée 1. Les serveurs d'une même paire couplée sont de la même couleur. Les câbles à retirer sont indiqués par une ligne en pointillés.

Le centre de données possède $N$ serveurs et $N$ câbles réseau qui relient un serveur à un autre. Chaque câble a une longueur en pieds. Le trafic circule dans les câbles réseau dans les deux sens et le centre de données est initialement connecté : pour chaque paire de serveurs $(u, v)$, il existe un chemin de câbles réseau allant de $u$ à $v$ (passant éventuellement par des serveurs intermédiaires). Vous avez audité le trafic réseau du centre de données et découvert que seules $K$ paires couplées de serveurs ont besoin de communiquer entre elles. (Notez que certains serveurs pourraient ne faire partie d'aucune paire couplée, ou pourraient faire partie de deux paires couplées ou plus.)

Vous devez maintenant retirer la plus grande longueur totale de câble possible du centre de données tout en maintenant toutes les paires couplées connectées entre elles : pour chaque paire de serveurs $(a, b)$, il doit exister un chemin de $a$ à $b$ passant par les câbles réseau originaux que vous avez conservés.

Trouvez la longueur totale minimale de câble qui doit être conservée pour satisfaire cette contrainte.

Entrée

La première ligne de l'entrée contient deux entiers séparés par un espace $N$ ($3 \le N \le 10^5$) et $K$ ($1 \le K \le 10^5$), le nombre de serveurs dans le centre de données et le nombre de paires couplées de serveurs que vous avez découvertes.

Les $N$ lignes suivantes décrivent les câbles réseau initialement présents dans le centre de données. Chaque ligne contient trois entiers séparés par un espace $u_i, v_i$ ($1 \le u_i, v_i \le N, u_i \neq v_i$), et $w_i$ ($1 \le w_i \le 10^9$), spécifiant qu'un câble relie le serveur $u_i$ au serveur $v_i$ et a une longueur de $w_i$ pieds. Il y a au plus un câble réseau reliant une paire de serveurs et le graphe des serveurs et des câbles est connexe.

Chacune des $K$ lignes suivantes contient deux entiers séparés par un espace $a_j$ et $b_j$ ($1 \le a_j, b_j \le N, a_j \neq b_j$) et décrit une paire couplée de serveurs. Chaque paire couplée doit rester connectée par un chemin après que vous ayez fini de retirer les câbles. Toutes les paires couplées sont distinctes ; $(a, b)$ et $(b, a)$ sont considérées comme identiques et ne seront pas toutes deux listées comme des paires couplées.

Sortie

Affichez un seul entier : la longueur totale minimale de câble réseau (en pieds) qui doit rester en place afin que toutes les $K$ paires de serveurs couplées restent connectées entre elles.

Exemples

Entrée 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

Sortie 1

57

Entrée 2

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

Sortie 2

9