24935번 - Travelling Caterpillar 다국어

Lilith is a hungry caterpillar! From her vantage point at the root of a tree, she has identified some leaves she wishes to munch before returning to the root. She wants to finish munching all of them as quickly as possible so that she will grow into a plump, buttery butterfly.

The tree Lilith occupies is a bit unusual. We can view it as a collection of nodes, where some of the nodes contain leaves that Lilith wishes to munch. Each branch connects exactly two nodes together. It is guaranteed that between every pair of nodes, there is precisely one way to travel from one to the other.

Given a description of the tree and which nodes have leaves that Lilith wishes to munch, can you help Lilith route her munching by minimizing the time she must travel?

The first line of input contains two integers $N$ ($1≤N≤1000$), which is the number of nodes in the tree, and $K$ ($1≤K≤N$), which is the number of leaves to be munched.

The next $N-1$ lines of input describe the branches (edges) of the tree. The $i$th such line contains three integers $s_i$, $t_i$ ($0≤s_i,t_i<N$, $s_i≠t_i$), and $d_i$ ($0≤d_i≤10^6$). This indicates there is a branch between node $s_i$ and node $t_i$ which takes $d_i$ time to cross. Furthermore, if we view the tree as rooted at node $0$, we have that $s_i$ is the parent of $t_i$ (i.e. $s_i$ lies on the unique path from $0$ to $t_i$). Lilith always starts at the root node $0$.

The last line of input contains $K$ distinct integers $a_1,\dots ,a_K$ ($0≤a_i<N$), which indicates the nodes containing leaves that Lilith wants to munch.

Display the length of the shortest path along the branches of the tree, starting and ending at the root, which allows Lilith to eat all leaves.