問題

祝日のない六月に ahri は有給休暇を使って「うしたぷにきあ王国」へ旅行したいと考えています。 「うしたぷにきあ王国」には $1, 2, ..., N$ の都市と$M$本の道があります。 $i$番目の道の情報について以下の「$t_i \ X_i \ Y_i$」形式で入力から与えられます。

• $1 \ Xi \ Yi$ ： $t_i=1$ のとき電車で都市$Xi$から都市$Yi$へ双方向に移動できる、移動毎にお金を10000消費する
• $2 \ Xi \ Yi$ ： $t_i=2$ のとき都市$Xi$から都市$Yi$へ双方向に歩いて移動できる、移動毎に体力を10000消費する

ahri は体力の消費を最小限にしつつ 都市$N$個のうち$K$個を $Z_1, Z_2, ..., Z_K$ まで順番に旅行したいと考えています。 旅行するために ahri が用意しなければならない最低金額を答えてください。

制約

• $2 \leqq N \leqq 10^4$
• $1 \leqq M \leqq \min(10^4, \frac{N(N-1)}{2})$
• $t_i = 1, 2$
• $1 \leqq X_i, Y_i \leqq N$
• $2 \leqq K \leqq 10$
• $Z_i \neq Z_j$
• 都市と道は単純グラフ
• 入力は整数

入力

$N \ M$

$t_1 \ X_1 \ Y_1$

$t_2 \ X_2 \ Y_2$

︙

$t_M \ X_M \ Y_M$

$K$

$Z_1 \ Z_2 \ ... \ Z_K$

出力

$Z_1, Z_2, ..., Z_K$ まで順番に旅行できる体力消費最小経路の中で最も低い金額を出力してください。

なお、$K$個の中に到達できない都市が存在する場合は $-1$ を出力してください。

サンプル

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

30000

ahri の目的は都市1から出発して都市4、都市5と旅行することです。

都市4から都市5へ移動するには歩くしかありませんが、都市1から都市4への移動は電車を使うことが出来ます。

したがって、都市1から出発して都市2、都市3、都市4と電車で移動し、都市4から都市5まで歩いて旅行するのが最善です。

お金は30000用意すれば良いです。

9 10
2 1 2
1 1 3
1 3 4
1 4 5
1 5 2
1 1 6
1 6 7
1 7 8
1 8 9
1 9 2
2
1 2

40000

都市2は都市1の隣にありますが ahri は歩きたくありません。

したがって、都市1から出発して都市3、都市4、都市5、都市2と移動して旅行するのが最善です。

他にも都市2へ到達する経路はありますが、40000以下にする方法はありません。

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

-1

目的地の都市に移動できないので $-1$ を出力します。

10 20
2 1 6
2 8 3
1 6 3
2 4 2
2 6 9
2 6 4
2 10 3
1 7 3
2 4 5
1 8 4
1 7 4
1 5 9
1 2 1
1 5 10
1 2 5
1 3 5
1 9 8
2 1 5
2 6 8
1 1 3
5
3 4 6 7 8

90000