Given a weighted undirected graph with $n$ vertices and $m$ edges. For each vertex $i$, you can pass through this vertex from time $t_i$ onwards. Given $q$ queries of the form $(x, y, t)$, find the shortest path from $x$ to $y$ at time $t$.
### Input
- The first line contains two integers $n, m$.
- The second line contains $n$ integers $t_i$. Ensure $0 \le t_1 \le t_2 \le \ldots \le t_n \le 1000$.
- The next $m$ lines each contain three integers $u, v, w$. Ensure there is at most one edge between any two vertices.
- The next line contains an integer $q$.
- The next $q$ lines each contain three integers $(x, y, t)$.
### Output
- For each query, print an integer representing the length of the shortest path, or print `-1` if no path exists.
### Constraints
- $1 \le n \le 500$.
- $1 \le m \le \frac{n \times (n - 1)}{2}$.
- $1 \le u \neq v \le n$.
- $1 \le w \le 10^4$.
- $1 \le q \le 5 \times 10^4$.
- $1 \le x \neq y \le n$.
- $0 \le t \le 1000$.
### Example
Input:
```
4 5
1 2 3 4
1 3 1
3 4 1
4 2 2
3 2 4
1 4 5
4
3 1 2
1 2 2
1 2 3
1 2 4
```
Output:
```
-1
-1
5
4
```
