Двунаправленное остовное дерево

Я наткнулся на этот вопрос на сайте интервьюstreet.com

Машины снова напали на королевство Сионов. Королевство Xions имеет N городов и N -1 двунаправленных дорог. Дорожная сеть так что существует единственный путь между любой парой городов.

Морфеус получил новости о том, что K Machines планируют уничтожить целое королевство. Эти Машины изначально живут в K разных городов королевства, и в любое время они могут планировать и запускать атака. Поэтому он попросил Нео разрушить некоторые дороги, чтобы нарушить связь между машинами, т.е. после разрушения этих дорог там не должно быть никаких путей между любыми двумя машинами.

Поскольку атака может быть совершена в любой момент, Нео должен выполнить это задание. как можно быстрее. Каждая дорога в королевстве занимает определенное время. быть уничтожены, и они могут быть уничтожены только по одному за раз.

Вам нужно написать программу, которая сообщает Нео минимальное количество времени. он потребует разорвать соединение между машинами.

Пример ввода Первая строка ввода содержит два символа, разделенных пробелом -. целые числа, N и K. Города пронумерованы от 0 до N -1. Затем следует N -1 строки, каждая из которых содержит три целых числа, разделенных пробелом -, x y z, которые означает, что существует двусторонняя дорога, соединяющая города x и города y, и чтобы разрушить эту дорогу, нужно z единиц времени. Затем следуйте K строк каждый из которых содержит целое число. Ith целое число — это идентификатор города, в котором находится i Машина находится в настоящее время.

Формат вывода Печатать в одной строке минимальное время, необходимое для нарушить связь между машинами.

Пример ввода

5 3
2 1 8
1 0 5
2 4 5
1 3 4
2
4
0

Пример вывода

10

Объяснение Нео может разрушить дорогу, соединяющую город 2 и город 4 в вес 5,и дорога, соединяющая города 0 и города 1 веса 5. Поскольку только одна дорога может быть разрушена за раз, общее минимальное время составляет 10 единиц времени. После разрушения этих дорог ни одна из Машин может добраться до другой машины любым путем.

Ограничения

2 <= N <= 100,000
2 <= K <= N
1 <= time to destroy a road <= 1000,000

Кто-нибудь может подсказать, как подойти к решению.