Problem Statement

Japan has $N$ airports numbered $1, 2, \dots, N$. AtCoder Airlines operates $M$ directed flight routes in Japan, numbered $1, 2, \dots, M$. Route $j$ goes from airport $A_j$ to airport $B_j$ and costs $C_j \times F$ yen.

Flying with AtCoder Airlines earns “miles.” You start with $0$ miles. Taking route $j$ once grants $C_j$ miles. At airport $i$, you can exchange miles for money at the rate $R_i$ yen per mile. Because of the constraint $0 \le R_i \le F-1$, endless profit cycles are impossible.

You can exchange a non-integral amount of miles or have a non-integral amount of money, but you cannot have a negative amount of miles or money.

What is the minimum initial amount of money in yen needed to fly from airport $1$ to airport $N$?

Solve $\mathrm{TESTCASES}$ test cases.

Constraints

• $1 \le \mathrm{TESTCASES} \le 40\,000$
• $2 \leq N \leq 400$
• $1 \leq M \leq N \times (N-1)$
• $1 \leq F \leq 100$
• $1 \leq A_j \leq N$
• $1 \leq B_j \leq N$
• $A_j \neq B_j$
• $(A_1, B_1), (A_2, B_2), \dots, (A_M, B_M)$ are all different.
• $1 \le C_j \le 100$
• $0 \le R_i \le F-1$
• It is possible to go from airport $1$ to airport $N$.
• The sum of $N^2$ over all test cases is at most $160\,000$.
• All input values are integers.

Input

The input is given from Standard Input in the following format, where $\mathrm{case}_k$ represents the $k$-th test case:

\mathrm{TESTCASES}
\mathrm{case}_1
\mathrm{case}_2
 \vdots
\mathrm{case}_{\mathrm{TESTCASES}}

Each test case is given in the following format:

N M
F
A_1 B_1 C_1
A_2 B_2 C_2
 \vdots
A_M B_M C_M
R_1 R_2 \cdots R_N

Output

Print $\mathrm{TESTCASES}$ lines. The $k$-th line should contain the minimum initial amount of money in yen needed to fly from airport $1$ to airport $N$ for the $k$-th test case.

Your output is considered as correct if its absolute or relative error is at most $10^{-6}$.