题目描述

给定一个有 $N$ 个顶点和 $M$ 条边的带权有向图，顶点编号为 $1$ 到 $N$，边编号为 $1$ 到 $M$。第 $i$ 条边（$1 \leq i \leq M$）从顶点 $u_i$ 连接到顶点 $v_i$（$u_i < v_i$），边的权重为 $w_i$。

此外，给定 $K$ 个整数三元组。第 $i$ 个（$1 \leq i \leq K$）三元组是 $(a_i, b_i, c_i)$（$a_i < b_i < c_i$）。

你从顶点 $1$ 出发，通过反复沿着边移动，最终到达顶点 $N$。

此外，对于所有 $i$（$1 \leq i \leq K$），如果你直接从顶点 $a_i$ 移动到顶点 $b_i$，那么接下来你必须移动到一个不同于顶点 $c_i$ 的顶点。

判断是否有可能到达顶点 $N$。如果有可能到达，同时计算你所经过边的权重之和的最小值。

输入格式

$$\begin{aligned} &N \ M \\ &u_1 \ v_1 \ w_1 \\ &u_2 \ v_2 \ w_2 \\ &\vdots \\ &u_M \ v_M \ w_M \\ &K \\ &a_1 \ b_1 \ c_1 \\ &a_2 \ b_2 \ c_2 \\ &\vdots \\ &a_K \ b_K \ c_K \end{aligned}$$

输入满足以下约束：

• 所有输入均为整数。
• $3 \leq N \leq 2 \times 10^5$
• $0 \leq M \leq 2 \times 10^5$
• $1 \leq u_i < v_i \leq N \ (1 \leq i \leq M)$
• $i \neq j \Rightarrow (u_i, v_i) \neq (u_j, v_j) \ (1 \leq i, j \leq M)$
• $1 \leq w_i \leq 10^9 \ (1 \leq i \leq M)$
• $0 \leq K \leq 2 \times 10^5$
• $1 \leq a_i < b_i < c_i \leq N \ (1 \leq i \leq K)$

输出格式

如果无法到达顶点 $N$，输出 $-1$。否则，输出你所经过边的权重之和的最小值。

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

4

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

9

3 2
1 2 1
2 3 1
1
1 2 3

-1

提示

在样例输入 1 中，最优移动路径是 $1 \rightarrow 3 \rightarrow 4$。

在样例输入 2 中，最优移动路径是 $1 \rightarrow 2 \rightarrow 4 \rightarrow 6 \rightarrow 7$。

翻译由 DeepSeek V3.2 完成