一家 GPS 导航公司 ICPC (International Control Perfection Company) 正在为交通网络设计一套汽车导航系统。该系统将交通网络抽象为一个带有边权 $c$ 的有向图 $G(V, E)$。对于一条有向边 $(u, v) \in E$，$c(u, v)$ 表示从地点 $u \in V$ 到另一个地点 $v \in V$ 的距离。公司希望在系统中实现最短路径模块。为了反映现实中交通路口无法向某些方向转弯的情况，我们需要找到一条不包含禁止转弯作为子路径的最短路径。

从 $v$ 到 $w$ 的路径是一个顶点序列 $(v_1, v_2, \dots, v_k)$，其中 $v_1 = v$，$v_k = w$，且对于 $1 \le i \le k-1$ 满足 $(v_i, v_{i+1}) \in E$。与路径的常见定义不同，这里允许路径中多次重复经过同一个顶点。路径的子路径是对应于该路径的序列的连续子序列。禁止转弯是指一个路径（即三元组）$(x, y, z)$，其中 $x, y, z \in V$ 且 $(x, y) \in E$ 以及 $(y, z) \in E$。路径 $(v_1, v_2, \dots, v_k)$ 的距离定义为 $\sum_{i=1}^{k-1} c(v_i, v_{i+1})$。从 $v \in V$ 到 $w \in V$ 的最短路径是指从 $v$ 到 $w$ 且距离最小的路径。公司希望找到两个指定顶点之间避开所有禁止转弯的最短路径距离。注意，从 $v \in V$ 到 $v \in V$ 的最短路径距离为 0，且它避开了所有禁止转弯。

请看下图中的示例。每条边的代价标注在边旁，禁止转弯列表在右侧框中。从顶点 3 到顶点 2 的避开禁止转弯的最短路径是 $(3, 0, 1, 5, 4, 1, 2)$，在下图中用蓝色箭头标出。该最短路径的距离为 $3 + 12 + 4 + 7 + 8 + 2 = 36$。注意，我们不能选择更短的路径 $(3, 0, 1, 2)$ 和 $(3, 0, 1, 5, 2)$，因为它们分别包含了禁止转弯 $(0, 1, 2)$ 和 $(1, 5, 2)$。

给定一个带有边权 $c$ 的有向图 $G(V, E)$、一组禁止转弯 $F$ 以及两个顶点 $v$ 和 $w$，编写一个程序输出从 $v$ 到 $w$ 避开所有禁止转弯的最短路径距离。我们假设每个顶点 $u$ 的出度（即从 $u$ 出发的边数）最多为 10。

输入格式

程序从标准输入读取数据。输入的第一行包含三个整数 $m$、$n$ 和 $k$ ($0 \le m \le 10n$, $1 \le n \le 30,000$, $0 \le k \le 500,000$)，其中 $m$ 是有向边的数量，$n$ 是顶点数量，$k$ 是给定有向图 $G(V, E)$ 中禁止转弯的数量。这里，$k$ 小于或等于给定有向图中所有可能禁止转弯的总数。顶点编号从 0 到 $n-1$。第二行包含两个整数 $v$ 和 $w$，分别表示起点和终点。在接下来的 $m$ 行中，第 $i$ 行包含三个整数 $x_i, y_i, c_i$ ($0 \le x_i \neq y_i \le n-1$ 且 $0 \le c_i \le 10^3$)，表示一条边 $(x_i, y_i) \in E$ 及其代价。在接下来的 $k$ 行中，第 $i$ 行包含三个整数 $x_i, y_i, z_i$，表示一个禁止转弯 $(x_i, y_i, z_i)$。

输出格式

程序向标准输出写入数据。仅打印一行。该行应包含一个整数，表示从 $v$ 到 $w$ 避开所有禁止转弯的最短路径距离。如果不存在这样的路径，则该行应包含 -1。

样例

输入 1

9 7 3
3 2
6 3 2
3 0 3
0 1 12
1 0 4
1 2 2
1 5 4
4 1 8
5 4 7
5 2 5
0 1 2
4 1 5
1 5 2

输出 1

36

输入 2

4 4 1
0 3
0 1 2
1 2 3
0 2 7
2 3 10
0 1 2

输出 2

17

输入 3

4 4 0
0 3
0 1 2
1 2 3
0 2 7
2 3 10

输出 3

15