AT_past19_m DAG ゲーム

给定一个有 $N$ 个顶点、$M$ 条边的简单有向图。顶点编号为 $1$ 到 $N$，边编号为 $1$ 到 $M$。第 $j$ 条边从顶点 $U_j$ 指向顶点 $V_j$。每个顶点有一个整数属性 point，第 $i$ 个顶点的 point 为 $P_i$。另外，每条边有一个实数属性 decay，取值范围为 $0$ 到 $1$，第 $j$ 条边的 decay 为 $W_j$。保证该图不存在有向环（即不存在从某个顶点 $i$ 沿着若干条边回到顶点 $i$ 的路径）。 高桥将在这个图上玩一个游戏。起初，顶点 $1$ 上有一个棋子，高桥的分数为 $0$。他进行如下操作，将棋子移动到顶点 $N$，同时累计分数。 1. 设当前棋子所在顶点编号为 $i$。将顶点 $i$ 的 point 值 $P_i$ 加到分数上。 2. 如果 $i=N$，则**成功**结束游戏。 3. 如果 $i$ 没有出边，则**失败**结束游戏。否则，从 $i$ 出发的边中选择一条。 4. 设选中的是第 $j$ 条边。将所有顶点的 point 值都乘以该边的 decay 值，即对每个 $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}$ 即视为正确。

### 样例解释 1 我们用 $P$ 表示 $(P_1, P_2, P_3, P_4)$。初始时 $P=(2,5,3,1)$。 若依次走 $1\rightarrow 3\rightarrow 4$，过程如下： 1. 把顶点 $1$ 的 point $P_1=2$ 加到分数上。 2. 从 $1$ 出发的边里，选第 $1$ 条边。 3. 所有顶点的 point 都乘以该边的 decay $W_1=0.5$，此时 $P=(1,2.5,1.5,0.5)$。 4. 棋子移到顶点 $3$。 5. 把顶点 $3$ 的 point $P_3=1.5$ 加到分数上。 6. 从 $3$ 出发的边里，选第 $4$ 条边。 7. 所有顶点的 point 都乘上该边的 decay $W_4=0.5$，此时 $P=(0.5,1.25,0.75,0.25)$。 8. 棋子移到顶点 $4$。 9. 把顶点 $4$ 的 point $P_4=0.25$ 加到分数上。 10. 游戏成功结束。 此时最终分数为 $2+1.5+0.25=3.75$，为最大可能值。 ### 样例解释 2 无法成功结束游戏。 ### 约束条件 - $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) \quad(j\neq k)$ - $0\leq W_j\leq 1$ - $W_j$ 是 $10^{-6}$ 的倍数，小数点后六位。 - 给定的图无有向环。 由 ChatGPT 5 翻译