题目内容

井下调度室要把一名巡检员从指定工位送到另一个工位。巷道里共有 $n$ 个工位，编号从 0 到 $n-1$。工位之间有两类通路：巷道需要按长度耗时行走；罐笼瞬时到达，但受安全规程限制。规程要求：全程最多乘坐 $c$ 次罐笼；两次罐笼之间必须至少走过一条巷道，不能连坐；从起点出发时可以直接先坐罐笼。请计算到达目标的最短耗时；若起点与终点是同一工位，耗时为 0；若无法到达，输出 -1。

巷道是双向的，第 $i$ 条连接工位 $x_i$ 与 $y_i$，耗时为 $d_i$（$d_i\ge `0`$）。罐笼也是双向的，第 $j$ 条连接工位 $a_j$ 与 $b_j$，耗时为 0。巷道和罐笼都可能出现重边或自环。

约束：

• 1 $\le$ $n$ $\le$ $10^4$
• 0 $\le$ $q$ $\le$ $2 \times 10^5$
• 0 $\le$ $b$ $\le$ 10
• 0 $\le$ $c$ $\le$ 10
• 0 $\le$ $d_i$ $\le$ 1000000000
• 0 $\le$ $s,t$ $<$ $n$

输入描述

第一行两个整数 $n$ 和 $q$（1 $\le$ $n$ $\le$ $10^4$，0 $\le$ $q$ $\le$ $2 \times 10^5$），表示工位数和巷道条数。

接下来 $q$ 行，每行三个整数 $x$、$y$、$d$（0 $\le$ $x,y$ $<$ $n$，0 $\le$ $d$ $\le$ 1000000000），表示一条双向巷道。

下一行一个整数 $b$（0 $\le$ $b$ $\le$ 10），表示罐笼条数。

接下来 $b$ 行，每行两个整数 $a$、$f$（0 $\le$ $a,f$ $<$ $n$），表示一条双向罐笼。

最后一行三个整数 $c$、$s$、$t$（0 $\le$ $c$ $\le$ 10，0 $\le$ $s,t$ $<$ $n$），表示罐笼次数上限、起点工位和终点工位。

输出描述

输出一个整数：最短耗时。若 $s=t$，输出 0。若无法到达，输出 -1。答案可能很大，请使用 64 位整数。

样例1

输入

5 4
0 1 7
1 2 7
2 3 7
3 4 7
2
0 2
2 4
2 0 4

输出

14

说明

先坐罐笼从 0 到 2（耗时 0），此时不能立刻再坐 2 到 4 的罐笼。沿巷道 2 $\to$ 3 $\to$ 4 耗时 7 $+$ 7 $=$ 14。全程只走巷道则要 28。

样例2

输入

4 1
0 1 9
0
0 2 2

输出

0

说明

起点和终点都是工位 2，不必移动。

样例3

输入

3 1
0 1 8
0
2 0 2

输出

-1

说明

工位 2 与 0、1 都不连通，无法到达。