Hongjun Likes Physics

Hongjun likes physics, and computing densities is his hobby.

After learning graph theory at school, Hongjun decided to define density on graphs as well. Take an undirected graph whose vertices and edges carry weights, let $SumV$ be the sum of the vertex weights and let $SumE$ be the sum of the edge weights. The density of that graph is $SumV / SumE$.

For his birthday, Myungwoo gave Hongjun an undirected graph with weights on the vertices and on the edges. Hongjun wants the induced subgraph of largest density.

An induced subgraph $G'(V', E')$ of a graph $G(V, E)$ satisfies the following conditions.

1. $V' \subseteq V$
2. The edge joining $u$ and $v$ belongs to $E'$ if and only if $u \in V'$, $v \in V'$, and that edge belongs to $E$.
3. The weights of the vertices and edges of $G'$ are the same as in $G$.
4. $G'$ is connected.

An induced subgraph with no edge has $SumE = 0$, so its density is undefined and it is not a candidate.

Help Hongjun and compute the density of the induced subgraph of maximum density.

The first line has the number of vertices $n$ and the number of edges $m$. ($2 \le n \le 500$, $1 \le m \le n(n-1)/2$)

The second line has $n$ integers separated by spaces, the weight of the $i$-th vertex. Every vertex weight is between $1$ and $10^6$.

Each of the next $m$ lines has three integers $u$, $v$, $c$, meaning that an edge of weight $c$ joins vertex $u$ and vertex $v$. Every edge weight is between $1$ and $1000$, and no edge is given twice. The vertices are numbered from $1$ to $n$.

Print the density of the induced subgraph of maximum density, rounded to six digits after the decimal point.

No input places the exact answer exactly halfway between two six-digit decimals, so the rounding direction is always determined.