AT_past19_m DAG ゲーム

You are given an $ N $ -vertex $ M $ -edge simple directed graph. The vertices are numbered $ 1 $ through $ N $ , and the edges are numbered $ 1 $ through $ M $ . Edge $ j $ directs from vertex $ U_j $ to vertex $ V_j $ . Each vertex has an integer attribute **point**: the point of vertex $ i $ is $ P_i $ . Also, each edge has a real attribute **decay** between $ 0 $ and $ 1 $ : the decay of edge $ j $ is $ W_j $ . It is guaranteed that the given graph does not have a closed cycle. (In other words, there is no way to travel from a vertex $ i $ along edges to go back to vertex $ i $ .) Takahashi is going to play a game on this graph. Initially, vertex $ 1 $ has a piece on it, and Takahashi's score is $ 0 $ . He performs the following procedure to move the piece to vertex $ N $ while accumulating his score. 1. Let $ i $ be the current number of vertex with the piece. Add the point $ P_i $ of vertex $ i $ to his score. 2. If $ i=N $ , he ends the game **successfully**. 3. If there is no edge going from vertex $ i $ , he ends the game **unsuccessfully**. Otherwise, choose an edge going from vertex $ i $ . 4. Let $ j $ be the number of the chosen edge. Multiply the point of each vertex by the decay of edge $ j $ . In other words, let $ P_i \leftarrow P_i\times W_j $ for each $ i\ (1\leq i\leq N) $ . 5. Move the piece to vertex $ V_j $ , and jump to step 1. Determine if he can end the game successfully. If it is possible, print the maximum possible final score of the game.

The input is given from Standard Input in the following format: > $ 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 $

Print the maximum possible final score if he can successfully end the game, and `-1` otherwise. In the former case, your answer is considered correct if the absolute or relative error from the true value is at most $ 10^{−6} $ .

### Sample Explanation 1 We denote the sequence $ (P_1,P_2,P_3,P_4) $ simply by $ P $ . Initially, $ P=(2,5,3,1) $ . If he moves the piece along vertices $ 1\rightarrow 3\rightarrow 4 $ , the game proceeds as follows. 1. Add the point $ P_1=2 $ of vertex $ 1 $ to his score. 2. Among the edges going from vertex $ 1 $ , choose edge $ 1 $ . 3. Multiply the point of each vertex by the decay $ W_1=0.5 $ of edge $ 1 $ . Now, $ P=(1,2.5,1.5,0.5) $ . 4. Move the piece to vertex $ V_1=3 $ . 5. Add the point $ P_3=1.5 $ of vertex $ 3 $ to his score. 6. Among the edges going from vertex $ 3 $ , choose edge $ 4 $ . 7. Multiply the point of each vertex by the decay $ W_4=0.5 $ of edge $ 4 $ . Now, $ P=(0.5,1.25,0.75,0.25) $ . 8. Move the piece to vertex $ V_4=4 $ . 9. Add the point $ P_4=0.25 $ of vertex $ 4 $ to his score. 10. He ends the game successfully. In this case, the final score is $ 2+1.5+0.25=3.75 $ , which is maximum possible. ### Sample Explanation 2 He cannot end the game successfully. ### Constraints - $ N,M,P_i,U_j $ , and $ V_j $ are integers. - $ 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 $ is a multiple of $ 10^{-6} $ and given with six decimal places. - The given graph does not have a directed cycle.