AT_agc072_e.[AGC072E] Flights 2

日本有 $N$ 个机场，每个机场编号为 $1, 2, \dots, N$。AtCoder 航空公司在日本运营着 $M$ 条航线，每条航线编号为 $1, 2, \dots, M$。航线 $j$ 从机场 $A_j$ 出发，抵达机场 $B_j$，票价为 $C_j \times F$ 日元。

乘坐 AtCoder 航空公司的飞机可以获得一种名为“里程（マイル）”的货币。初始时你拥有 $0$ 里程。每乘坐一次航线 $j$，你可以获得 $C_j$ 里程。此外，在机场 $i$，每 $1$ 里程可以兑换 $R_i$ 日元。由于有约束 $0 \leq R_i \leq F-1$，所以无法通过不断换乘飞机来无限制地获得金钱。

需要注意的是，兑换的里程数和所持金可以不是整数，但不能为负数。

现在，想要通过飞机从机场 $1$ 到达机场 $N$，你最少需要准备多少日元的初始资金？

请你解答 $\mathrm{TESTCASES}$ 个测试用例。

输入通过标准输入给出，格式如下，其中 $\mathrm{case}_k$ 表示第 $k$ 个测试用例。

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

每个测试用例格式如下：

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

请输出 $\mathrm{TESTCASES}$ 行。第 $k$ 行输出第 $k$ 个测试用例中，为了能够通过飞机从机场 $1$ 到达机场 $N$，所需的最小初始资金。

当你的答案与标准答案的绝对误差或相对误差不超过 $10^{-6}$ 时，视为正确。

约束条件

• $1 \leq \mathrm{TESTCASES} \leq 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)$ 均互不相同
• $1 \leq C_j \leq 100$
• $0 \leq R_i \leq F-1$
• 存在从机场 $1$ 到机场 $N$ 的路径
• 所有测试用例的 $N^2$ 之和不超过 $160\,000$
• 所有输入均为整数

样例解释 1

如果初始资金为 $146$ 日元，可以按如下方式从机场 $1$ 到达机场 $3$：

1. 乘坐航线 $1$，从机场 $1$ 到机场 $2$。所持金变为 $146 - 70 = 76$ 日元，获得 $7$ 里程。
2. 在机场 $2$，将 $7$ 里程兑换为 $14$ 日元。所持金变为 $76 + 14 = 90$ 日元。
3. 乘坐航线 $2$，从机场 $2$ 到机场 $3$。所持金变为 $90 - 90 = 0$ 日元，获得 $9$ 里程。
   如果初始资金少于 $146$ 日元，则无法从机场 $1$ 到达机场 $3$。

样例解释 2

如果初始资金为 $106$ 日元，可以按如下方式从机场 $1$ 到达机场 $4$：

1. 乘坐航线 $1$，从机场 $1$ 到机场 $2$。所持金变为 $106 - 70 = 36$ 日元，获得 $7$ 里程。
2. 乘坐航线 $3$，从机场 $2$ 到机场 $3$。所持金变为 $36 - 10 = 26$ 日元，获得 $1$ 里程。
3. 在机场 $3$，将 $8$ 里程兑换为 $72$ 日元。所持金变为 $26 + 72 = 98$ 日元。
4. 乘坐航线 $4$，从机场 $3$ 到机场 $2$。所持金变为 $98 - 10 = 88$ 日元，获得 $1$ 里程。
5. 在机场 $2$，将 $1$ 里程兑换为 $2$ 日元。所持金变为 $88 + 2 = 90$ 日元。
6. 乘坐航线 $2$，从机场 $2$ 到机场 $4$。所持金变为 $90 - 90 = 0$ 日元，获得 $9$ 里程。
   如果初始资金少于 $106$ 日元，则无法从机场 $1$ 到达机场 $4$。

由 ChatGPT 4.1 翻译