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} $ 以下の場合、正答とみなされます。

### Sample Explanation 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 $ に行くことはできません。 ### Sample Explanation 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 $ に行くことはできません。 ### Constraints - $ 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 $ 以下である - 入力される値はすべて整数