CF444A DZY Loves Physics

DZY 喜欢物理，他喜欢计算密度。 几乎所有的东西都有密度，甚至图也有。我们定义一个无向图（图的节点与边都有权值）的密度如下：  其中 $v$ 为节点权值之和，$e$ 为边权值之和。DZY 有一个图 $G$，现在他想在图中找出一个连通的诱导子图 $G'$，使得 $G'$ 的密度最大。 一个图 $G(V,E)$ 的诱导子图 $G'(V',E')$ 满足： - ； - 当且仅当  时，边  属于 $E'$，其中边  属于 $E$； - $G'$ 中每条边与每个节点的权值与 $G$ 中相应的边和节点的权值相同。 请你帮助 DZY 找出密度最大的诱导子图。注意，选出的诱导子图必须是连通的。 

第一行包含两个用空格分隔的整数 $n$（$1\le n\le 500$），$m$，$n$ 表示图 $G$ 的节点数，$m$ 表示图的边数。 第二行包含 $n$ 个用空格分隔的整数 $x_{i}$（$1\le x_{i}\le 10^{6}$），其中 $x_{i}$ 表示第 $i$ 个节点的权值。节点编号为 $1$ 到 $n$。 接下来 $m$ 行，每行含有三个用空格分隔的整数 $a_{i}, b_{i}, c_{i}$（$1\le a_{i} < b_{i} \le n$；$1\le c_{i} \le 10^{3}$），表示在 $a_{i}$ 与 $b_{i}$ 之间有一条权值为 $c_{i}$ 的边。图中不会有重边。

输出一个实数，表示答案，绝对误差或相对误差不超过 $10^{-9}$。

在第一个样例中，你只能选择空子图，或仅包含第 $1$ 个节点的子图。 在第二个样例中，选择整个图是最优的。 由 ChatGPT 5 翻译