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: $\left\{\begin{array}{ll}{\frac{v}{e}} & {(e > 0)} \\{0} & {(e = 0)} \end{array} \right.$ 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:  $V^{\prime} \subseteq V$;  edge $(a, b) \in E^{\prime}$ if and only if $a \in V^{\prime}, b \in V^{\prime}$, and edge $(a, b) \in E$;  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. [Image] 


-----Input-----

The first line contains two space-separated integers n (1 ≤ n ≤ 500), $m(0 \leq m \leq \frac{n(n - 1)}{2})$. 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}.


-----Examples-----
Input
1 0
1

Output
0.000000000000000

Input
2 1
1 2
1 2 1

Output
3.000000000000000

Input
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

Output
2.965517241379311



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

Difficulty: competition

Starter code:

Solutions:
"""
Codeforces Round 254 Div 1 Problem A

Author  : chaotic_iak
Language: Python 3.3.4
"""

def read(mode=2):
    # 0: String
    # 1: List of strings
    # 2: List of integers
    inputs = input().strip()
    if mode == 0:
        return inputs
    if mode == 1:
        return inputs.split()
    if mode == 2:
        return [int(x) for x in inputs.split()]

def write(s="\n"):
    if isinstance(s, list): s = " ".join(map(str,s))
    s = str(s)
    print(s, end="")

################################################### SOLUTION
n,m = read()
v = read()
best = 0
for i in range(m):
    a,b,c = read()
    temp = (v[a-1] + v[b-1]) / c
    best = max(best, temp)
print(best)

n,m = map(int,input().split())
a = list(map(int,input().split()))
ans = 0
for i in range(m):
    ax,bx,x = map(int,input().split())
    ans = max(ans,(a[ax-1]+a[bx-1])/x)
print(ans)

n,m = [int(x) for x in input().split()]

l = [int(x) for x in input().split()]

x = 0;
for i in range(m):
    a,b,c = [int(x) for x in input().split()]
    cur = (l[a-1]+l[b-1])/c
    #print(a,b,c,cur)
    if cur > x: x = cur
print("%0.15f"%x)


a = input().split(' ')
n = int(a[0])
m = int(a[1])
b = input().split(' ')
a.clear()
for i in range(0, n) :
    a.append(int(b[i]))
ans = 0
for i in range(0, m) :
    b = input().split(' ')
    c = []
    for j in range(0, 3) : 
        c.append(int(b[j]))
    ans = max(ans, (a[c[0] - 1] + a[c[1] - 1]) / c[2])
print(ans)


n, m=list(map(int, input().split()))
ans=0
f=list(map(int, input().split()))
for i in range(m):
    a, b, x=list(map(int, input().split()))
    ans=max(ans, (f[a-1]+f[b-1])/x)
print(ans)


R = lambda:map(int, input().split())
ans = 0
n, m = R()
F = list(R())
for i in range(m):
	a, b, x = R()
	ans = max(ans, (F[a - 1]+ F[b - 1]) / x)
print(ans)

[n,m] = list(map(int, input().split(" ")))
V = list(map(int, input().split(" ")))
wyn = 0.0
for i in range(m):
    [a,b,c] = list(map(int, input().split(" ")))
    wyn = max(wyn, (V[a-1]+V[b-1])/c)
print(wyn)

n, m = map(int, input().split())
t, v = 0, [0] + list(map(int, input().split()))
for i in range(m):
    x, y, d = map(int, input().split())
    t = max(t, (v[x] + v[y]) / d)
print(t)

N, E = 0, 0
Cost, Edges = [], []
Answer = 0.0

def Solve():
    nonlocal Answer
    for e in Edges:
        Answer = max(Answer, (1.0 * (Cost[e[0]] + Cost[e[1]]) / (1.0 * e[2])))

def ReadInput():
    nonlocal N, E, Cost, Edges
    N, E = list(map(int, input().split()))
    Cost = list(map(int, input().split()))
    for i in range(0, E):
        x, y, c = list(map(int, input().split()))
        Edges.append((x - 1, y - 1, c))

def PrintOutput():
    print(Answer)

def main():
    ReadInput()
    Solve()
    PrintOutput()

main()


from sys import stdin

input = stdin.readline

n, m = map(int, input().split())
vs = [int(i) for i in input().split()]
ans = 0.0
for _ in range(m):
	a, b, c = map(int, input().split())
	if c:
		ans = max(ans, (vs[a-1] + vs[b-1]) / c)
print(ans)

n,m=list(map(int,input().split()));a=list(map(int,input().split()));o=0.0

for i in range(m):

    x,y,c=list(map(int,input().split()));o=max(o,(a[x-1]+a[y-1])/c)

print(o)





# Made By Mostafa_Khaled


# HEY STALKER
n, m = map(int, input().split())
l = list(map(int, input().split()))
ans = 0
for t in range(m):
    x, y, c = map(int, input().split())
    ans = max(ans, (l[x-1] + l[y-1]) / c)
print(ans)