给定一个包含 $n$ 个顶点和 $m$ 条边的加权有向图，顶点编号从 $1$ 到 $n$，边编号从 $1$ 到 $m$。第 $j$ 条边（$1 \le j \le m$）从顶点 $u_j$ 指向顶点 $v_j$（满足 $u_j < v_j$），其权重为 $w_j$。

此外，给定 $k$ 个整数三元组。第 $i$ 个（$1 \le i \le k$）三元组为 $(a_i, b_i, c_i)$（满足 $a_i < b_i < c_i$）。

袋鼠从顶点 $1$ 出发，通过重复沿边移动前往顶点 $n$。此外，对于所有 $i$（$1 \le i \le k$），如果袋鼠直接从顶点 $a_i$ 移动到顶点 $b_i$，那么它下一步必须移动到一个不是 $c_i$ 的顶点。

确定袋鼠是否能够到达顶点 $n$。如果可以，计算袋鼠路径上边权之和的最小值。

输入格式

第一行包含两个整数 $n$ 和 $m$：分别为图中的顶点数和边数（$3 \le n \le 2 \cdot 10^5$；$0 \le m \le 2 \cdot 10^5$）。

接下来的 $m$ 行中，第 $j$ 行包含三个整数 $u_j, v_j$ 和 $w_j$：分别为第 $j$ 条边的起点、终点及其权重（$1 \le u_j < v_j \le n$；对于 $i \neq j$ 有 $(u_i, v_i) \neq (u_j, v_j)$；$1 \le w_j \le 10^9$）。

接下来一行包含一个整数 $k$：禁止三元组的数量（$0 \le k \le 2 \cdot 10^5$）。

接下来的 $k$ 行，每行包含三个整数：$a_i, b_i$ 和 $c_i$（$1 \le a_i < b_i < c_i \le n$）。你可以假设边 $(a_i, b_i)$ 和 $(b_i, c_i)$ 在图中均存在。

输出格式

如果无法到达顶点 $n$，输出 $-1$。否则，输出袋鼠路径上边权之和的最小值。

样例

样例输入 1

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

样例输出 1

6

样例输入 2

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

样例输出 2

9

样例输入 3

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

样例输出 3

-1