P15716 [JAG 2023 Summer Camp #2] Drifting

You are given a weighted directed graph of $N$ vertices and $M$ edges, with vertices numbered $1$ to $N$ and edges numbered $1$ to $M$. The $i$-th ($1 \leq i \leq M$) edge connects from vertex $u_i$ to vertex $v_i$ ($u_i < v_i$), and the weight of the edge is $w_i$. Also, $K$ triplets of integers are given. The $i$-th ($1 \leq i \leq K$) triplet is $(a_i, b_i, c_i)$ ($a_i < b_i < c_i$). You start at vertex $1$ and move to vertex $N$ by repeatedly moving along an edge. In addition, for all $i$ ($1 \leq i \leq K$), if you move from vertex $a_i$ to vertex $b_i$ directly, we must next move to a vertex other than vertex $c_i$. Judge whether it is possible to reach vertex $N$. If it is possible to reach, also calculate the minimum sum of the weights of the edges you pass through.

$$ \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} $$ The input satisfies the following constraints. - All inputs consist of integers. - $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)$

If you cannot reach vertex $N$, output $-1$. Otherwise, output the minimum sum of the weights of the edges you pass through.

In Sample Input 1, the best move is $1 \rightarrow 3 \rightarrow 4$. In Sample Input 2, the best move is $1 \rightarrow 2 \rightarrow 4 \rightarrow 6 \rightarrow 7$.