DZY 热爱物理,他喜欢计算密度。
几乎所有东西都有密度,甚至是图表。我们将无向图(图的节点和边都有一些值)的密度定义如下:
$$\begin{案例}
\dfrac{v}{e} & (e > 0) \\
0 & (e = 0)
\end{案例}$$
一旦DZY得到了图G,现在他想找到该图的连通诱导子图G',使得G'的密度尽可能大。
图 G(V, E) 的导出子图 G'(V', E') 是满足以下条件的图:
- $$V' \subseteq V$$;
- 边 $$(a,b)\in E^{T}$$ 当且仅当 $$a \in V'、b \in V'$$ 且边 $$(a,b)\in E$$;
- G' 中的边的值与 G 中相应边的值相同,节点的值也是如此。
帮助DZY找到密度最大的诱导子图。请注意,您选择的诱导子图必须是连接的。
输入
第一行包含两个空格分隔的整数 n (1 ≤ n ≤ 500), $$m \left( 0 \leq m \leq \frac{n(n-1)}{2} \right)$$。整数n表示图G的节点数,m表示边数。
第二行包含 n 个空格分隔的整数 xi (1 ≤ xi ≤ 106),其中 xi 表示第 i 个节点的值。考虑图节点的编号从 1 到 n。
接下来的 m 行包含三个空格分隔的整数 ai、bi、ci(1 ≤ ai < bi ≤ n;1 ≤ ci ≤ 103),表示节点 ai 和 bi 之间值为 ci 的边。该图不会包含多条边。
输出
输出一个表示答案的实数,绝对或相对误差最多为 10 - 9。
示例
输入 #1
1 0 1
输出 #1
0.000000000000000
输入 #2
2 1 1 2 1 2 1
输出 #2
3.000000000000000
输入 #3
5 6 13 56 73 98 17 1 2 56 1 3 29 1 4 42 2 3 95 2 4 88 3 4 63
输出 #3
2.965517241379311
注意
在第一个示例中,您只能选择空子图,或者仅包含节点 1 的子图。
在第二个示例中,选择整个图是最佳的。