题目描述

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.

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

提示

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$.