A9507. DZY Loves Physics

DZY loves Physics, and he enjoys calculating density.

Almost everything has density, even a graph. We define the density of a non-directed graph (nodes and edges of the graph have some values) as follows:

 where $v$ is the sum of the values of the nodes, $e$ is the sum of the values of the edges.Once DZY got a graph $G$ , now he wants to find a connected induced subgraph $G'$ of the graph, such that the density of $G'$ is as large as possible.

An induced subgraph $G'(V',E')$ of a graph $G(V,E)$ is a graph that satisfies:

- ;
- edge  if and only if , and edge ;
- the value of an edge in $G'$ is the same as the value of the corresponding edge in $G$ , so as the value of a node.

Help DZY to find the induced subgraph with maximum density. Note that the induced subgraph you choose must be connected.


The first line contains two space-separated integers $n (1<=n<=500)$ , . Integer $n$ represents the number of nodes of the graph $G$ , $m$ represents the number of edges.

The second line contains $n$ space-separated integers $x_{i} (1<=x_{i}<=10^{6})$ , where $x_{i}$ represents the value of the $i$ -th node. Consider the graph nodes are numbered from $1$ to $n$ .

Each of the next $m$ lines contains three space-separated integers $a_{i},b_{i},c_{i} (1<=a_{i}<b_{i}<=n; 1<=c_{i}<=10^{3})$ , denoting an edge between node $a_{i}$ and $b_{i}$ with value $c_{i}$ . The graph won't contain multiple edges.

Output a real number denoting the answer, with an absolute or relative error of at most $10^{-9}$ .

In the first sample, you can only choose an empty subgraph, or the subgraph containing only node $1$ .

In the second sample, choosing the whole graph is optimal.