最佳旅游路线

Time Limit: 1000 ms

Memory Limit: 65535 ms

Description

N个城市,编号从1N,他们之间通过N-1条双向道路相连,虽然只有N-1条道路,却能保证任何两个城市能相互到达。现在SA来到了标号为X的城市,他手里有张地图,地图上是一个城市集m1,m2,m3…mj,其中每个城市都是不同的,并且与X也不同。现在SA想从X开始访问完所有的城市,当然正如你说想的那样,每条道路都有一个花费,现在的问题当然是想让总的花费最小。

即将参加ChengDu Regional的童鞋们,能帮忙解决这个问题么?

Input

第一行包含两个数N,X,意义如上所述。(2<= N<=50000,1 <=X<=N) 接下来下面N-1行,每行包含3个整数 A B C,代表A城市和B城市直接相连,费用为C。(1<= A,B<= N,1<= C<= 1000) 接下来一个数j(1<= j <= N - 1),代表城市集上共有j个城市。 接下来一行,包含j个不同的整数m1,m2,m3…mj,代表SA想去的城市。 注意:SA的访问顺序不一定按照m1,m2,m3…mj的顺序进行。

Output

输出最小费用

Sample Input

4 2
1 2 1
4 2 2
2 3 3
2
1 3

Sample Output

5

Hint

Source

from friend

提交代码