AT_agc072_e [AGC072E] Flights 2

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.

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 $

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

### Sample Explanation 1 If you start with $ 146 $ yen, you can go from airport $ 1 $ to airport $ 3 $ : 1. Take route $ 1 $ to go from airport $ 1 $ to airport $ 2 $ . You now have $ 146-70=76 $ yen, and get $ 7 $ miles. 2. At airport $ 2 $ , exchange $ 7 $ miles for $ 14 $ yen. You now have $ 76+14=90 $ yen. 3. Take route $ 2 $ to go from airport $ 2 $ to airport $ 3 $ . You now have $ 90-90=0 $ yen, and get $ 9 $ miles. If you start with less than $ 146 $ yen, you cannot go to airport $ 3 $ . ### Sample Explanation 2 If you start with $ 106 $ yen, you can go from airport $ 1 $ to airport $ 4 $ : 1. Take route $ 1 $ to go from airport $ 1 $ to airport $ 2 $ . You now have $ 106-70=36 $ yen, and get $ 7 $ miles. 2. Take route $ 3 $ to go from airport $ 2 $ to airport $ 3 $ . You now have $ 36-10=26 $ yen, and get $ 1 $ mile. 3. At airport $ 3 $ , exchange $ 8 $ miles for $ 72 $ yen. You now have $ 26+72=98 $ yen. 4. Take route $ 4 $ to go from airport $ 3 $ to airport $ 2 $ . You now have $ 98-10=88 $ yen, and get $ 1 $ mile. 5. At airport $ 2 $ , exchange $ 1 $ mile for $ 2 $ yen. You now have $ 88+2=90 $ yen. 6. Take route $ 2 $ to go from airport $ 2 $ to airport $ 4 $ . You now have $ 90-90=0 $ yen, and get $ 9 $ miles. If you start with less than $ 106 $ yen, you cannot go to airport $ 4 $ . ### 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.