Byteasar 正从 Bitingham 前往 Byteburg。他希望在途中参观一些必看景点，包括一些有趣的古迹、精致的餐厅以及众多其他旅游景点。他参观这些地点的顺序并非完全无关紧要。例如，Byteasar 不希望在 Digitest 享用丰盛的晚餐后立即攀登 Bitfork 城堡的尖塔；同样，他宁愿在晚餐后去 Zip City（有些人称之为 Sip City）喝一杯著名的 Compresso 咖啡，而不是在晚餐前。幸运的是，他的行程在一定程度上是灵活的，他可以在几种顺序之间进行选择。由于油价高昂，为了经济起见，他希望走尽可能短的路线。请作为好朋友帮助他确定满足其要求的最短路径长度。

道路系统由 $n$ 个地点和连接它们的 $m$ 条道路组成。地点编号从 $1$ 到 $n$，道路编号也从 $1$ 到 $m$。每条道路连接一对不同的地点，且是双向的。得益于巧妙的立交桥和隧道系统，不同的道路仅在地点（即它们的端点）处相交，而在地点之外不会交叉。每条道路都有一定的长度。一对地点之间最多可以直接由一条道路连接，尽管它们之间可能存在许多由至少两条直接道路组成的路径。

设 $k$ 为 Byteasar 想要参观的地点数量。Bitingham 的编号为 $1$，Byteburg 的编号为 $n$，而 Byteasar 想要参观的地点编号为 $2, 3, \dots, k+1$。

图中展示了一个示例道路系统。假设 Byteasar 想要参观地点 2、3、4 和 5，并且他希望在 3 之前参观 2，在 3 之后参观 4 和 5。那么最短路线经过地点 1、2、4、3、4、5、8，其长度为 19。

请注意，地点 4 在路线中出现在地点 3 之前和之后。这是完全可以的，意味着 Byteasar 在访问地点 3 之前不会在那里停留，因为他的要求不允许这样做。然而，他被允许在访问地点 3 之前经过地点 4 而不进行停留——而这正是他将要做的！

编写一个程序：

• 从标准输入读取道路系统的描述、Byteasar 选择参观的地点列表以及关于他想要参观这些地点的顺序限制；
• 确定以适当顺序经过所有选定地点的最短路线长度；
• 将结果写入标准输出。

输入格式

标准输入的第一行包含三个整数 $n$、$m$ 和 $k$，由空格分隔，$2 \le n \le 20\,000$，$1 \le m \le 200\,000$，$0 \le k \le 20$；此外，满足不等式 $k \le n-2$。

接下来的 $m$ 行包含道路的描述，每行一条。第 $(i+1)$ 行包含三个整数 $p_i$、$q_i$ 和 $l_i$，由空格分隔，$1 \le p_i < q_i \le n$，$1 \le l_i \le 1\,000$。这些数字表示连接地点 $p_i$ 和 $q_i$ 的长度为 $l_i$ 的道路。你可以确信对于每组测试数据，从 Bitingham 到 Byteburg 以及到 Byteasar 想要参观的每个地点都是可达的。

在第 $(m+1)$ 行有一个整数 $g$ ($0 \le g \le \frac{k(k-1)}{2}$)，这是关于 Byteasar 想要参观其所选地点顺序的限制数量。这些限制在接下来的 $g$ 行中给出，每行一条。第 $(m+i+1)$ 行包含两个整数 $r_i$ 和 $s_i$，由空格分隔，$2 \le r_i \le k+1$，$2 \le s_i \le k+1$，$r_i \neq s_i$。这对数字 $r_i$ 和 $s_i$ 意味着 Byteasar 想要在访问 $s_i$ 之前访问 $r_i$。然而，这并不妨碍他在访问 $r_i$ 之前经过 $s_i$，也不妨碍他在访问 $s_i$ 之后经过 $r_i$。只要他不进行停留和参观旅游景点，他可以自由地这样做。保证对于每组测试数据，至少存在一种满足所有限制的参观所选地点的顺序。

输出格式

在标准输出的第一行也是唯一一行中，写入一个整数，即从 Bitingham 出发，按适当顺序经过所有选定地点的最短路径长度。

样例

输入 1

8 15 4
1 2 3
1 3 4
1 4 4
1 6 2
1 7 3
2 3 6
2 4 2
2 5 2
3 4 3
3 6 3
3 8 6
4 5 2
4 8 6
5 7 4
5 8 6
3
2 3
3 4
3 5

输出 1

19