Description

在一张由 $n$ 个点，$m$ 条边组成的无向图上，有两个内鬼，和 $k$ 个目标对象，现在内鬼想要抓捕所有的目标对象。 无向图的边，可以由一个三元组 $(x,y,w)$ 表示表示有一条连接 $(x,y)$ 的边，需要花 $w$ 个时刻的时间。 现在内鬼捕获了 $e$ 条情报，每一条是一个三元组$(p,x,t)$，表示第 $p$ 个对象会出现在第 $t$ 时刻第 $x$ 个点。如果在 $t$ 时刻有 任何一个 内鬼在第 $x$ 个点，那么就能把第 $p$ 个对象抓出。蹲点是被允许的，即你可以在 $t$ 时刻前到达第 $x$ 个点，不过一定要等到时刻 $t$ 才可以进行抓捕。如果有多个对象，可以同时进行抓捕。这里值得注意的是，这是内鬼抓捕对象的唯一方式。在其余任何时刻无论是否撞见了对象，我们都不能将其抓捕。 现在给出两个内鬼的位置，问在最后决策下，内鬼最快在哪一个时刻可以把所有目标对象都捕获。

Format

Input

第一行一个整数 $T$，表示数据组数。 每一组数据包括以下输入： 第一行三个整数 $n,m,k$，表示的是 $n$ 个点，$m$ 条边，$k$ 个目标对象。 接下来 $m$ 行，每行三个数 $x,y,w(1 \le x,y \le n,1\le w\le 10^4)$ 表述一条边。 接下来一行一个数 $e$，表示情报条数。 接下来 $e$ 行，每行一个三元组 $(p,x,t) (1\le x \le n, 1 \le p \le k)$，意义见题目表述。 最后一行两个整数 $x,y(1\le x,y\le n)$，表示一开始两个内鬼的位置。

Output

输出一个数，表示最快的时刻。如果永远都抓不到所有的目标对象，则输出"-1"(不包含引号)。

Samples

1
3 1 3
1 2 1
4 
1 2 1
1 3 2
2 2 1
3 3 2
1 3

2

见附加文件。

Limitation

以下的 $t$ 是 $(p,x,t)$ 三元组中 $t$ 的最大值。

对于 $20\%$ 的数据，保证 $k=1$。

对于 $100\%$ 的数据，保证 $1\le \sum n \le 10^4,1\le \sum m \le 2 \times 10^4, 1\le \sum e \le 10^5, 1\le k \le 8, 1\le t \le 10^8$。

时空限制：3000ms/256MB。