注意

この問題は実行時間制限が厳しいので、高速な言語を使用することを推奨しています。 （C++, C#, PyPy3 で AC できることが確認されています。）

動画

問題文

$N$ 頂点からなる木があります。この木の頂点には $1$ から $N$ までの番号がついていて、辺には $1$ から $N-1$ までの番号がついています。

辺 $i(1\le i\le N-1)$ は、頂点 $u_i$ と頂点 $v_i$ を結ぶ、長さが $l_i$ の辺です。

正整数 $C$ と、長さ $Q$ の頂点列 $(x_1,x_2,\dots ,x_Q)$ が与えられます。

イカはいま頂点 $x_1$ にいて、これから $Q-1$ 個の頂点 $x_2,\dots ,x_Q$ を順番に訪れようとしています。

イカは次の $3$ つの行動から $1$ つを選んで行うことを繰り返します。

• 現在いる頂点に接続する辺を $1$ つ選び、その辺が結ぶもう $1$ つの頂点へ移動する。

  • この行動には選んだ辺の長さ $l_i$ だけ時間がかかる。

• 現在いる頂点にジャンプビーコンを $1$ 個設置する。

  • すでに木に設置されているビーコンがある場合、それは消滅し、現在位置のビーコン $1$ 個だけが残る。

  • この行動には時間はかからない。

• ジャンプビーコンが設置されている頂点に移動する。

  • ジャンプビーコンは消滅する。

  • この行動には $C$ だけ時間がかかる。

イカが $Q-1$ 個の頂点を順番に訪れるのにかかる時間の最小値を求めてください。

入力

$N$ $Q$ $C$
$u_1$ $v_1$ $l_1$
$u_2$ $v_2$ $l_2$
$⋮$
$u_{N-1}$ $v_{N-1}$ $l_{N-1}$
$x_1$ $x_2$ $\dots$ $x_Q$

• $2\le N,Q\le \mathrm{3,000}$
• $1\le C\le {10}^9$
• $1\le u_i,v_i\le N(1\le i\le N-1)$
• $1\le l_i\le {10}^9(1\le i\le N-1)$
• 与えられるグラフは木である。
• $1\le x_i\le N(1\le i\le Q)$
• $x_i\ne x_{i+1}(1\le i\le Q-1)$
• 入力はすべて整数である。

出力

イカが $Q-1$ 個の頂点を順番に移動するのにかかる時間の最小値を出力せよ。 最後に改行せよ。

サンプル

3 5 1
1 2 1000
2 3 10
1 3 2 3 1

1031

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

22

2 10 1
1 2 1000000000
2 1 2 1 2 1 2 1 2 1

5000000004