Among Us 是一款由美国游戏工作室 Innersloth 开发并发布的在线多人社交推理游戏。玩家被投放到一艘宇宙飞船中，每个玩家被指定为船员（crewmate）或冒充者（impostor）的私人角色。在本题中，恰好有 2 名冒充者和最多 8 名船员。冒充者需要杀死所有船员才能赢得游戏，而船员则需要尽可能快地完成任务。

地图上有 $n$ 个房间。游戏开始时，每个玩家会出生在某个房间。玩家每秒有两个选择：原地不动或移动到另一个房间。冒充者有 $m$ 条无向秘密路径可以移动，每条路径连接两个房间，通过它需要花费一定的时间。在本题中，船员可以在房间之间自由移动，而冒充者只能使用这 $m$ 条秘密路径。

由于冒充者非常聪明，他们可以预测某些船员在某些时刻的位置。当一名船员按照预测出现在某个房间，且至少有一名冒充者也在该房间时，冒充者可以在不消耗时间的情况下杀死该船员。冒充者还预测船员将在 $t_{\max}$ 秒内完成所有任务。也就是说，如果至少有一名船员在 $t_{\max}$ 秒后仍然存活，冒充者将输掉游戏。基于这些预测，请计算冒充者杀死所有船员所需的最短时间（如果可能的话）。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 100$)，表示测试用例的数量。

每个测试用例的第一行包含三个整数 $n, m, k$ ($1 \le n \le 10^4, 1 \le m \le 2 \times 10^4, 1 \le k \le 8$)，分别表示房间数、秘密路径数和船员数。

接下来的 $m$ 行，每行包含三个整数 $u, v, w$ ($1 \le u, v \le n, u \neq v, 1 \le w \le 10^4$)，表示有一条连接房间 $u$ 和 $v$ 的秘密路径，冒充者通过它需要恰好 $w$ 秒。

下一行包含两个整数 $e$ 和 $t_{\max}$ ($1 \le e \le 10^5, 1 \le t_{\max} \le 10^8$)，表示预测的数量和船员完成所有任务的时间。

接下来的 $e$ 行，每行包含三个整数 $p, x, t$ ($1 \le p \le k, 1 \le x \le n, 1 \le t \le t_{\max}$)，表示船员 $p$ 将在游戏开始后 $t$ 秒出现在房间 $x$。

每个测试用例的最后一行包含两个整数 $x$ 和 $y$ ($1 \le x, y \le n$)，表示两名冒充者在游戏开始时分别出生在房间 $x$ 和 $y$。

保证所有测试用例的 $\sum n \le 10^4, \sum m \le 2 \times 10^4, \sum e \le 10^5$。

输出格式

对于每个测试用例，输出冒充者杀死所有船员所需的最短时间，占一行。如果冒充者无法赢得游戏，则输出 $-1$。

样例

输入 1

4
5 7 3
1 2 1
2 3 2
2 4 1
3 4 5
4 5 1
5 2 5
5 1 5
3 8
1 5 3
3 4 2
2 2 4
3 1
3 1 2
1 2 1
3 3
1 2 1
2 2 1
1 2 2
2 3
3 1 2
1 2 1
3 3
1 2 1
2 2 1
1 2 2
3 3
10 10 8
1 2 1
2 3 1
3 4 1
4 5 1
5 6 1
6 7 1
7 8 1
8 9 1
9 10 1
10 1 1
8 10
1 2 1
2 3 2
3 4 3
4 5 4
5 7 1
6 8 2
7 9 3
8 10 4
1 6

输出 1

4
1
-1
4