在一个遥远的国家里有 $l$ 个城市，编号为 $0,1,\cdots,l-1$，围着一个大湖建成一圈。城市内和城市间有很多交通线路，并且它们都是双向的。

每个城市里都有 $n$ 个火车站，编号为 $0,1,\cdots,n-1$，由 $m$ 条动车线路相连。由于这些城市是一起修建的，所以任意两个城市内的火车站连接情况完全一致，即点集和边集都相等。

有些火车站是枢纽站。如果火车站 $s$ 在某个城市是枢纽站，那么所有城市的 $s$ 号火车站都是枢纽站。相邻城市的编号相同的枢纽站会被高铁线路连接。

一场天灾之后，所有这些线路都需要重建才可以被投入使用。由于城市之间非常相似，重建的费用也很有规律，具体如下：

• 每个城市 $i$ 都有两个正整数 $a_i,b_i$ 。
• 每条动车线路都有一个正整数 $d_j$ ，不同城市的同一条动车线路的 $d_j$ 相等。
• $i$ 号城市的 $j$ 号动车线路的重建费用是 $b_i+d_j$ 。
• $i$ 号城市和 $(i+1)\bmod l$ 号城市之间的任意一条高铁线路的重建费用都是 $a_i$ 。

你需要花费尽可能少的代价，重建若干条线路，使得国家里的任意两个火车站可以互达。

输入格式

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

接下来 $m$ 行，每行三个整数 $u_j,v_j,d_j$ ，描述一条连接 $u_j$ 和 $v_j$ 的动车线路。

接下来一行一个正整数 $l$ 。

接下来 $l$ 行，每行两个正整数 $a_i,b_i$ ，描述一个城市。

接下来一行一个正整数 $r$ ，表示一个城市里枢纽站的个数。

最后 $r$ 行，每行一个非负整数 $s_k$ ，表示每个城市的 $s_k$ 号火车站是枢纽站。

输出格式

一行一个正整数，表示使得所有火车站两两互达的最小代价。

样例一

input

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

output

24

样例二

input

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

output

76

样例三、四

见下发文件。

数据范围与提示

对于所有数据，$2\le n\le 10^4, 1\le m\le 10^5, 0\le u_i,v_i,s_k<n, 1\le d_j,a_i,b_i\le 10^9, 3\le l\le 10^5, 1\le r\le n$ ，图中无重边自环且连通，$s_k$ 两两不同。

时间限制：$\texttt{1s}$

空间限制：$\texttt{1024MB}$