AT_past19_m DAG ゲーム

$ N $ 頂点 $ M $ 辺の単純有向グラフが与えられます。 頂点には $ 1 $ から $ N $ までの番号が、辺には $ 1 $ から $ M $ までの番号がそれぞれ付けられており、辺 $ j $ は頂点 $ U_j $ から頂点 $ V_j $ に向かって伸びています。 各頂点には**得点**と呼ばれる整数値が定まっており、頂点 $ i $ の得点は $ P_i $ です。 また、各辺には**減衰率**と呼ばれる $ 0 $ 以上 $ 1 $ 以下の実数値が定まっており、辺 $ j $ の減衰率は $ W_j $ です。 なお、与えられるグラフには有向閉路が存在しないことが保証されます（すなわち、ある頂点 $ i $ からいくつか辺を辿って再び頂点 $ i $ に戻ってくる方法は存在しません）。 高橋君はこのグラフ上でゲームをしようとしています。 最初、頂点 $ 1 $ にコマが $ 1 $ つおいてあり、高橋君のスコアは $ 0 $ です。 高橋君は、今から以下のように操作を行うことで、コマを頂点 $ N $ まで動かしながらスコアを増やしていきます。 1. 現在コマが置いてある頂点の番号を $ i $ とする。頂点 $ i $ の得点 $ P_i $ をスコアに加算する。 2. $ i=N $ ならばゲームを**成功**として終了する。 3. 頂点 $ i $ から伸びている辺が存在しないならば、ゲームを**失敗**として終了する。そうでないならば、頂点 $ i $ から伸びている辺を $ 1 $ 本選ぶ。 4. 選んだ辺の番号を $ j $ とする。各頂点の得点に辺 $ j $ の減衰率をかける。すなわち、各 $ i\ (1\leq i\leq N) $ に対して $ P_i \leftarrow P_i\times W_j $ とする。 5. コマを頂点 $ V_j $ に動かし、1. に戻る。 高橋君がゲームを成功として終了させることが可能かどうか判定し、可能ならばゲーム終了時におけるスコアの最大値を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ P_1 $ $ P_2 $ $ \dots $ $ P_N $ $ U_1 $ $ V_1 $ $ W_1 $ $ U_2 $ $ V_2 $ $ W_2 $ $ \vdots $ $ U_M $ $ V_M $ $ W_M $

高橋君がゲームを成功として終了させることが可能ならばゲーム終了時におけるスコアの最大値を、不可能ならば `-1` を出力せよ。 なお、前者の場合、真の値との絶対誤差または相対誤差が $ 10^{−6} $ 以下であれば正解として扱われる。

### Sample Explanation 1 以下、数列 $ (P_1,P_2,P_3,P_4) $ のことを簡単に $ P $ と表記します。 最初、 $ P=(2,5,3,1) $ です。 コマを頂点 $ 1\rightarrow 3\rightarrow 4 $ と動かすとき、ゲームは以下のように進行します。 1. 頂点 $ 1 $ の得点 $ P_1=2 $ をスコアに加算する。 2. 頂点 $ 1 $ から伸びている辺のうち辺 $ 1 $ を選ぶ。 3. 各頂点の得点に辺 $ 1 $ の減衰率 $ W_1=0.5 $ をかける。 $ P=(1,2.5,1.5,0.5) $ になる。 4. コマを頂点 $ V_1=3 $ に動かす。 5. 頂点 $ 3 $ の得点 $ P_3=1.5 $ をスコアに加算する。 6. 頂点 $ 3 $ から伸びている辺のうち辺 $ 4 $ を選ぶ。 7. 各頂点の得点に辺 $ 4 $ の減衰率 $ W_4=0.5 $ をかける。 $ P=(0.5,1.25,0.75,0.25) $ になる。 8. コマを頂点 $ V_4=4 $ に動かす。 9. 頂点 $ 4 $ の得点 $ P_4=0.25 $ をスコアに加算する。 10. ゲームを成功として終了する。 このとき、ゲーム終了時におけるスコアは $ 2+1.5+0.25=3.75 $ となり、これが最大値です。 ### Sample Explanation 2 ゲームを成功として終了させることはできません。 ### Constraints - $ N,M,P_i,U_j,V_j $ は整数 - $ 2\leq N \leq 10^5 $ - $ 1\leq M \leq 10^5 $ - $ 1\leq P_i\leq 10^4 $ - $ U_j \neq V_j $ - $ (U_j,V_j)\neq (U_k, V_k)\ (j\neq k) $ - $ 0\leq W_j\leq 1 $ - $ W_j $ は $ 10^{-6} $ の倍数であり、小数点以下第 $ 6 $ 位まで与えられる - 与えられるグラフに有向閉路は存在しない