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:

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}.

提交代码