I. Bobs Rating
time limit per test
3 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Given a graph with $$$N$$$ vertices and $$$M$$$ unordered edges. Each edge $$$i$$$ has a passing rating of $$$W_i$$$ and connects vertices $$$U_i$$$ and $$$V_i$$$.

Bob is allowed to move from one vertex to another using edges. Bob can use the $$$i$$$-th edge if and only if his rating is greater than or equal to $$$W_i$$$. He can use the same edge and visit the same vertex as many times as he wants.

Whenever Bob is located at vertex $$$x$$$, he has two options for gaining a new rating:

  • He can gain $$$A_x$$$ rating for free. He can use this option only once during his journey.
  • He can gain $$$1$$$ rating for $$$C_x$$$ coins. He can use this option as many times as he wants throughout his journey.

Bob now has $$$Q$$$ queries. For each query $$$i$$$, answer the following question:

  • Bob has an initial rating of $$$R_i$$$ and is located at vertex $$$S_i$$$. He is planning to reach vertex $$$T_i$$$. What is the minimum number of coins required for this?

Print $$$-1$$$ if he cannot reach vertex $$$T_i$$$ even with an infinite number of coins.

Input
  • The first line contains one integer $$$T \ (1 \leq T \leq 100)$$$, the number of test cases.
  • Then, for each test case:
    • The first line contains three space-separated integers $$$N, M, Q$$$ $$$(1 \leq N, M, Q \leq 5 \cdot 10^5)$$$.
    • The second line contains $$$N$$$ space-separated integers $$$A_1, A_2, \ldots, A_N$$$ $$$(1 \leq A_i \leq 10^6)$$$.
    • The third line contains $$$N$$$ space-separated integers $$$C_1, C_2, \ldots, C_N$$$ $$$(1 \leq C_i \leq 10^6)$$$.
    • Then, $$$M$$$ lines follow, each containing three space-separated integers $$$U_i, V_i, W_i$$$ $$$(1 \leq U_i, V_i \leq N; 1 \leq W_i \leq 10^{12})$$$.
    • Then, $$$Q$$$ lines follow, each containing three space-separated integers $$$S_i, T_i, R_i$$$ $$$(1 \leq S_i, T_i \leq N; 1 \leq R_i \leq 10^{12})$$$.

It is guaranteed that the sum of $$$N$$$ across all test cases does not exceed $$$5 \cdot 10^5$$$.

It is guaranteed that the sum of $$$M$$$ across all test cases does not exceed $$$5 \cdot 10^5$$$.

It is guaranteed that the sum of $$$Q$$$ across all test cases does not exceed $$$5 \cdot 10^5$$$.

Output

For each test case, print $$$Q$$$ lines, each consisting of one integer, the answer for that query.

Example
Input
1
5 5 4
5 2 4 3 10
1 2 3 4 5
3 3 10
1 2 5
3 4 7
1 3 13
2 5 21
4 5 3
2 2 4
1 4 2
5 2 10
Output
11
0
4
5