​在一座小岛上，有一片神奇的森林，每一年这里都会出现宝藏。

​宝藏出现的出现位置只可能是 $N$ 个位置中的一个。

​在接下来的 $Q$ 年里，小可可要去寻找宝藏。

​由于小可可不会飞，所以他要乘直升机前往。

​森林会发生变化，小可可会选择最方便着陆的位置着陆，第 $i$ 年小可可要在第 $s_i$ 个位置着陆。

​森林很茂密，小可可只能步行前进。他找到了 $M$ 条可以尝试通过的小路，第 $i$ 条小路连接第 $a_i$ 和第 $b_i$ 个位置， 小可可期望要花 $c_i$ 的时间通过。此外，凭借小可可自身的力量，他不能够开拓任何道路。

​除了有坎坷的路，森林中还有结界。

​每个结界可以控制一个位置，使小可可不能进出这个位置。

​要破解结界，小可可需要找到对应的晶石。用晶石敲击结界，结界就会瓦解。

​每个结界对应的晶石是唯一的。

​小可可可以同时带着多块晶石。

森林中一共有 $k$ 个结界。

​其中第 $i$ 个结界控制着第 $v_i$ 个位置，对应的晶石放在第 $z_i$ 个位置。

​每一年，结界都会被重置。也就是说，所有结界都会恢复，并且所有晶石都会回到原来的位置。

​虽然森林会发生变化，但是所有的道路，结界，晶石的位置以及各种属性都不会变化，那 $N$ 个位置也不会改变，森林的变化只会影响到在每个位置上着陆的方便程度。

​由于小可可是有备而来，所以他肯定会带藏宝图，也就是说，他知道宝藏的具体位置。第 $i$ 年宝藏的位置是 $t_i$。

​小可可想知道，他每一年能否找到宝藏，以及他每一年从直升机着陆到找到宝藏，期望的步行时间至少是多少。

​特殊地，如果小可可的降落位置被结界控制，那么他就没法降落，于是他也一定找不到宝藏。

输入格式

​第一行三个非负整数 $N, M, k$。

​接下来 $M$ 行，每行三个正整数 $a_i, b_i, c_i$。

​接下来 $k$ 行，每行两个正整数 $v_i, z_i$。

​第 $M+k+2$ 行是一个正整数 $Q$。

​接下来 $Q$ 行，每行两个正整数 $s_i, t_i$。

输出格式

​输出 $Q$ 行，每行一个整数。

​对于第 $i$ 行输出第 $i$ 年的答案。

​如果小可可不能找到宝藏，输出 $-1$，否则输出一个整数表示小可可从直升机着陆到找到宝藏，最少的期望步行时间。

13 15 2
1 2 6
2 3 2
2 4 3
3 4 3
1 5 6
1 6 4
5 7 3
6 7 2
3 8 1
1 9 9
9 10 2
9 11 6
10 12 3
11 12 4
12 13 5
12 7
10 4
4
10 1
5 13
13 12
8 13

-1
33
-1
44

样例 1 解释

​如图。

​其中位置的编号和每条路的期望步行时间已标出，三角形表示晶石，正方形表示结界，以颜色对应。

​对于第一组询问，由于 $10$ 号点有结界，小可可无法降落，所以答案为 $-1$。

​对于第二组询问，沿着路径 $5 \to 7 \to 6 \to 1 \to 9 \to 11 \to 12 \to 13$ 走，期望步行时间为 $33$。

​对于第三组询问，由于小可可无法破解位于 $12$ 号点的结界，所以答案为 $-1$。

​对于第四组询问，沿着路径 $8 \to 3 \to 4 \to 2 \to 1 \to 6 \to 7 \to 6 \to 1 \to 9 \to 10\to 12 \to 13$ 走，期望步行时间为 $44$。

​可以证明，对于上面两组答案不为 $-1$ 的询问，不存在一种方案使得有更短的期望步行时间。

样例 2

见选手目录下的 treasure/treasure2.in 和 treasure/treasure2.ans。

样例 3

见选手目录下的 treasure/treasure3.in 和 treasure/treasure3.ans。

数据范围

​对于所有数据，保证 $N \leq 400$，$M \leq 10^5$，$k \leq 16$，$Q \leq 2\times 10^5$，$1 \leq v_i, z_i \leq N$，$1 \leq s_i, t_i \leq N$。

​测试点 $1\sim 1$ 满足 $k = 0$。

​测试点 $2\sim 3$ 满足 $N \leq 20$，$k \leq 4$。

​测试点 $4\sim 6$ 满足 $N \leq 50$，$k \leq 7$。

​测试点 $7\sim 10$ 满足 $N \leq 250$，$k \leq 10$，$s_i = 1$。

​测试点 $11\sim 14$ 满足 $N \leq 250$，$k \leq 10$。

​测试点 $15\sim 16$ 满足 $k \leq 14$。

​测试点 $17\sim 18$ 满足 $k \leq 15$。

​测试点 $19\sim 20$ 无特殊限制。