题目描述

小 D 有一张 $n$ 个点 $m$ 条边的无向带权图 $G$，第 $i$ 条边连接 $u_i$ 和 $v_i$，权值为 $w_i$。

小 D 还得到了两个长度为 $k$ 的序列 $x,y$，以及集合 $S \subseteq [0,n)$。

小 D 又建了一张新的图 $H$，一共 $nk$ 个点，点用二元组 $(a,b)$（$a \in [0,k),\ b \in [0,n)$）表示。

新的图的边集中恰包含以下几种边：

1. 对于 $a \in [0,k),\ i \in [0,m)$，存在边连接 $(a,u_i)$ 和 $(a,v_i)$，权值为 $w_i+y_a$。
2. 对于 $a \in [0,k-1),\ i \in S$，存在边连接 $(a,i)$ 和 $(a+1,i)$，权值为 $x_a$。
3. 对于 $i \in S$，存在边连接 $(k-1,i)$ 和 $(0,i)$，权值为 $x_{k-1}$。

求图 $H$ 的最小生成树的权值。

输入格式

第一行两个整数 $n,m$。

接下来 $m$ 行，每行三个整数 $u_i,v_i,w_i$。

接下来一行一个整数 $k$。

接下来 $k$ 行，每行两个整数 $x_i,y_i$。

接下来一行一个整数 $r$，表示集合 $S$ 的大小。

接下来 $r$ 行，每行一个整数，表示集合 $S$ 的元素。

输出格式

一行一个整数，表示最小生成树权值和。

样例一

输入

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

输出

24

样例二

输入

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

输出

76

数据范围

子任务编号	$n,m,k \le$	特殊性质	分值
1	$1000$	无	$12$
2	$10^5$	$x_i=0$	$14$
3		$y_i=0$	$19$
4		$m=n-1,\ r=n$	$23$
5		无	$32$

对于所有数据，

$$1 \le n,m \le 10^5,\quad 2 \le k \le 10^5,$$ $$0 \le u_i,v_i < n,\quad 0 \le w_i,x_i,y_i \le 10^8,$$$$1 \le r \le n,\quad 0 \le s_i < n.$$

$s_i$ 互不相同，保证 $H$ 连通。