题目描述

ICPC 王国的中心有一个巨大的圆形湖泊，所有的城市都围绕着湖泊发展，形成一个城市的环形结构。由于所有城市都按照相同的城市规划发展，这些城市非常相似。它们拥有完全相同的地铁网络。它们的一些车站也是城际高铁的车站，连接相邻城市中两个对应的车站。所有的列车线路都是在两个终点站之间提供双向交通，没有任何中间站。

各个城市拥有相同数量的地铁站和地铁线路。在每个城市，车站被依次编号为 $0, 1, 2, \dots$。在一个城市中，两个车站是否由地铁线路连接，仅取决于它们的车站编号，而与城市无关。如果在一个城市中，车站 $v$ 与车站 $u$ 相连，那么在所有其他城市中也是如此。在所有城市中，车站 $v$ 和 $u$ 之间的行驶距离都是相同的。

所有城市的高铁车站编号列表完全相同。如果车站 $s$ 在一个城市中是高铁车站，那么在所有其他城市中也是如此。相邻两个城市中，所有具有相同编号的高铁车站对都由高铁线路连接。如果车站 $s$ 是一条高铁线路的一端，那么相邻城市中的车站 $s$ 就是另一端。不存在其他高铁线路。在王国中，可以通过一条或多条地铁和/或高铁线路在任意两个车站之间旅行。

由于近年来的财政困难，王国计划停用部分地铁和高铁线路，以降低铁路系统的维护成本。维护成本是地铁线路和高铁线路的维护成本之和。一条地铁线路的维护成本是依赖于城市的基本成本和与该线路行驶距离成比例的成本之和。一条高铁线路的维护成本仅取决于其连接的两个城市。

你的任务是制定一个停用部分线路的计划，使得总维护成本最小化。当然，在停用之后，王国中任意两个车站仍然需要通过一条或多条地铁和/或高铁线路相连。

输入

输入由以下格式的单个测试用例组成。

$$n\ m \\ v_1\ u_1\ d_1 \\ \vdots \\ v_m\ u_m\ d_m \\ l \\ a_0\ b_0 \\ \vdots \\ a_{l-1}\ b_{l-1} \\ r \\ s_1 \\ \vdots \\ s_r $$

这里，$n$ 是一个满足 $2 \leq n \leq 10^4$ 的整数，表示每个城市中的地铁站数量。每个城市中的车站编号从 $0$ 到 $n-1$。$m$ 是一个满足 $1 \leq m \leq 10^5$ 的整数，表示每个城市中的地铁线路数量。接下来的 $m$ 行是一个城市中地铁系统的信息。第 $i$ 行包含三个整数 $v_i$，$u_i$ 和 $d_i$，满足 $0 \leq v_i < n$，$0 \leq u_i < n$，$v_i \ne u_i$，以及 $1 \leq d_i \leq 10^9$。它们表示一条地铁线路连接编号为 $v_i$ 和 $u_i$ 的车站，其与行驶距离成比例的维护成本为 $d_i$。任意两个车站之间最多有一条地铁线路。一个城市中的所有地铁站通过一条或多条地铁线路直接或间接相连。

下一行的 $l$ 是一个满足 $3 \leq l \leq 10^5$ 的整数，表示王国中的城市数量。城市编号从 $0$ 到 $l - 1$，且城市 $0$ 也称为城市 $l$。对于每个 $0 \leq j \leq l - 1$，城市 $j$ 和城市 $j + 1$ 相邻。接下来的 $l$ 行中的 $a_j$ 和 $b_j$ 是满足 $1 \leq a_j \leq 10^9$ 和 $1 \leq b_j \leq 10^9$ 的整数。$a_j$ 是连接城市 $j$ 和 $j + 1$ 的高铁线路的维护成本。$b_j$ 是城市 $j$ 中地铁线路的基本维护成本。

$r$ 是一个满足 $1 \leq r \leq n$ 的整数，表示每个城市中的高铁车站数量。$s_1$，$s_2$，...，$s_r$ 是每个城市中高铁车站的编号。

输出

在一行中输出一个整数，表示在最小化成本并保持所有车站直接或间接相连的情况下，铁路系统在停用部分线路后的最小维护成本。

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

24

3 3
0 1 7
1 2 8
2 0 5
4
8 1
5 1
9 3
7 3
2
1
2

76

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

120