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.

Input

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

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

Note

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.