[Usaco2007 Dec]奶牛的旅行

作为奶牛们辛勤工作的回报，农场主约翰（Farmer John）决定带她们去附近的大城市游玩一天。旅行前夜，奶牛们兴奋地讨论着如何充分利用这次难得的闲暇时光。

幸运的是，奶牛们找到了一张详细的城市地图。地图上标出了城市中的 $L$ 座标志性建筑，编号依次为 $1$ 到 $L$，以及连接这些建筑的 $P$ 条道路。按照计划，当天早晨，约翰会开车将奶牛们送到她们指定的某座建筑旁；当奶牛们完成旅行并回到出发点后，他再将她们接回农场。

由于城市中的道路都很狭窄，所有道路均为通行方向固定的单行道。

对于编号为 $i$ 的标志性建筑，参观它可以为奶牛们带来 $F_i$ 的乐趣值。与在道路上行走所花费的时间相比，参观建筑的耗时可以忽略不计。

第 $i$ 条道路从建筑 $L1_i$ 通向建筑 $L2_i$，奶牛们走完这条道路需要 $T_i$ 的时间。

奶牛们希望选择一条从某座建筑出发、最终回到该建筑的旅行路线，使整段旅行中平均每单位时间获得的乐趣值最大。同一座建筑只会贡献一次乐趣值：即使奶牛们多次经过同一座建筑，也只能获得一次该建筑的乐趣值。

为了让奶牛们得到足够的锻炼，约翰要求她们至少参观 $2$ 座不同的建筑。

请计算奶牛们能够获得的最大平均乐趣值。保证城市道路图中至少存在一个经过 $2$ 座或更多不同建筑的有向环，因此奶牛们一定能够满足要求并回到出发点。

输入格式

第一行包含 $2$ 个以空格分隔的整数 $L$ 和 $P$，分别表示标志性建筑的数量和道路的数量。

接下来 $L$ 行，第 $i$ 行包含一个整数 $F_i$，表示参观编号为 $i$ 的建筑可以获得的乐趣值。

接下来 $P$ 行，第 $i$ 行包含 $3$ 个以空格分隔的整数 $L1_i$、$L2_i$ 和 $T_i$，表示第 $i$ 条道路从建筑 $L1_i$ 通向建筑 $L2_i$，走完该道路需要 $T_i$ 的时间。

输出格式

输出一个实数，保留到小数点后 $2$ 位，表示奶牛们能够获得的最大平均乐趣值。直接输出结果，不进行任何特殊的取整操作。

样例输入

5 7
30
10
10
5
10
1 2 3
2 3 2
3 4 5
3 5 2
4 5 5
5 1 3
5 2 2

样例输出

6.00

数据范围

• $2\le L\le 1000$；
• $2\le P\le 5000$；
• $1\le F_i\le 1000$；
• $1\le T_i\le 1000$；
• 城市道路图中至少存在一个经过 $2$ 座或更多不同建筑的有向环。

来源与许可

本题为 USACO 2007 December 试题「奶牛的旅行」，题面与测试数据整理自 BZOJ。

样例 1

输入

5 7
30
10
10
5
10
1 2 3
2 3 2
3 4 5
3 5 2
4 5 5
5 1 3
5 2 2

输出

6.00