P2868 [USACO07DEC] Sightseeing Cows G

农夫约翰决定奖励他的奶牛们的辛勤工作，带它们去大城市游览！奶牛们必须决定如何最好地度过它们的空闲时间。 幸运的是，它们有一张详细的城市地图，显示了 $L$ $(2 \leq L \leq 1000)$ 个主要地标（方便地编号为 $1$ 到 $L$）和 $P$ $(2 \leq P \leq 5000)$ 条连接这些地标的单向牛道。农夫约翰会把奶牛们送到它们选择的一个起始地标，从那里它们将沿着牛道走到一系列其他地标，最后回到它们的起始地标，农夫约翰会在那里接它们回农场。由于城市空间有限，牛道非常狭窄，因此每条牛道的旅行只能沿着一个固定方向进行。 虽然奶牛们可以在城市里待多久都行，但它们很容易感到无聊。参观每个新的地标很有趣，但在它们之间行走需要时间。奶牛们知道每个地标 $i$ 的确切乐趣值 $F_i$ $(1 \leq F_i \leq 1000)$。 奶牛们还了解牛道。牛道 $i$ 连接地标 $L1_i$ 到 $L2_i$（方向为 $L1_i \to L2_i$），需要时间 $T_i$ $(1 \leq T_i \leq 1000)$ 来穿越。 为了度过一个最好的假期，奶牛们希望最大化它们旅行的单位时间平均乐趣值。当然，地标只有在第一次访问时才有趣；奶牛们可以多次经过地标，但它们不会再次感受到它的乐趣值。此外，农夫约翰要求奶牛们至少访问两个地标，以便在假期中得到一些锻炼。 帮助奶牛们找到它们能够实现的最大单位时间乐趣值。

第 $1$ 行：两个用空格分隔的整数：$L$ 和 $P$ 第 $2$ 行到第 $L+1$ 行：第 $i+1$ 行包含一个整数：$F_i$ 第 $L+2$ 行到第 $L+P+1$ 行：第 $L+i+1$ 行描述牛道 $i$，包含三个用空格分隔的整数：$L1_i$，$L2_i$ 和 $T_i$

第 $1$ 行：一个保留两位小数的数字（不要进行显式四舍五入），表示最大可能的单位时间平均乐趣值，如果奶牛们无法按照上述规则计划任何旅行，则输出 $0$。

（由 ChatGPT 4o 翻译）