Description

You are given an undirected graph with $n$ vertices and $m$ edges, where each edge has a weight.

You need to find a shortest path from $1$ to $n$ that, while satisfying the given $g$ constraints, can stop at every vertex numbered from $2$ to $k+1$.

Each constraint is of the form $r_i, s_i$, meaning that you must have stopped at $r_i$ before stopping at $s_i$.

Note that “stop” here does not mean merely passing through.

Input Format

The first line contains three integers $n, m, k$.

Each of the next $m$ lines contains three integers $p_i, q_i, l_i$, meaning there is an edge of weight $l_i$ between $p_i$ and $q_i$.

The next line contains an integer $g$.

Each of the next $g$ lines contains two integers $r_i, s_i$, representing one constraint.

Output Format

Output a single integer on one line — the length of the shortest path.

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

19

Hint

Constraints:

• For $100\%$ of the testdata, the following hold:
• $2 \le n \le 2 \times 10^4$.
• $1 \le m \le 2 \times 10^5$.
• $0 \le k \le \min(20, n-2)$.
• $1 \le p_i < q_i \le n$.
• $1 \le l_i \le 10^3$.
• $r_i, s_i \in [2, k+1],\ r_i \ne s_i$.
• There are no multiple edges, and a solution always exists.

Translated by ChatGPT 5