P15716 [JAG 2023 Summer Camp #2] Drifting

给定一个有 $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$。否则，输出你所经过边的权重之和的最小值。

在样例输入 1 中，最优移动路径是 $1 \rightarrow 3 \rightarrow 4$。 在样例输入 2 中，最优移动路径是 $1 \rightarrow 2 \rightarrow 4 \rightarrow 6 \rightarrow 7$。 翻译由 DeepSeek V3.2 完成