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 翻译