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: MEDIUM_HARD
Tags: Mathematics

Greedy algorithms
Skill types: Greedy algorithms

Starter code:

Solutions:
(n, m) = map(int, input().split())
a = list(map(int, input().split()))
o = 0.0
for i in range(m):
	(x, y, c) = map(int, input().split())
	o = max(o, (a[x - 1] + a[y - 1]) / c)
print(o)


(v, e) = map(int, input().split())
vertex = list(map(int, input().split()))
ret = 0.0
for i in range(e):
	(a, b, c) = map(int, input().split())
	a -= 1
	b -= 1
	ret = max(ret, (vertex[a] + vertex[b]) / c)
print(ret)


from sys import stdin
input = stdin.readline
(n, m) = map(int, input().split())
arr = [int(i) for i in input().split()]
res = 0.0
for _ in range(m):
	(a, b, c) = map(int, input().split())
	if c:
		res = max(res, (arr[a - 1] + arr[b - 1]) / c)
print(res)


(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()


import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
x = list(map(int, input().split()))
ans = 0
for _ in range(m):
	(u, v, c) = map(int, input().split())
	if ans < (x[u - 1] + x[v - 1]) / c:
		ans = (x[u - 1] + x[v - 1]) / c
print(ans)


import sys

def input():
	return sys.stdin.readline().strip()
(n, m) = map(int, input().split())
w = list(map(int, input().split()))
ans = 0.0
for i in range(m):
	(u, v, c) = map(int, input().split())
	ans = max(ans, round((w[u - 1] + w[v - 1]) / c, 9))
print(ans)


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) = 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) = map(int, input().split())
v = list(map(int, input().split()))
ans = 0
for i in range(m):
	(a, b, c) = map(int, input().split())
	ans = max(ans, (v[a - 1] + v[b - 1]) / c)
print(ans)


(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, m) = input().split()
a = [0] + list(map(float, input().split()))
ans = 0
for _ in range(int(m)):
	(u, v, c) = input().split()
	ans = max(ans, (a[int(u)] + a[int(v)]) / float(c))
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)


s = input()
n = int(s.split()[0])
m = int(s.split()[1])
v = [int(x) for x in input().split()]
mx = 0
for i in range(m):
	s = input().split()
	a = (v[int(s[0]) - 1] + v[int(s[1]) - 1]) / int(s[2])
	if mx < a:
		mx = a
print(mx)


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


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


(nodes, edges) = map(int, input().split())
nodesValues = list(map(int, input().split()))
answer = 0
for i in range(edges):
	(a, b, c) = map(int, input().split())
	answer = max(answer, (nodesValues[a - 1] + nodesValues[b - 1]) / c)
print(answer)


(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)


import sys

def input():
	return sys.stdin.readline().strip()
(n, m) = map(int, input().split())
x = [int(i) for i in input().split()]
edge = []
val = 0
for i in range(m):
	(a, b, c) = map(int, input().split())
	val = max((x[a - 1] + x[b - 1]) / c, val)
print(val)


import math

def solve():
	(n, m) = [int(i) for i in input().split()]
	vw = [int(i) for i in input().split()]
	M = 0.0
	for _ in range(m):
		(a, b, c) = [int(i) for i in input().split()]
		M = max(M, (vw[a - 1] + vw[b - 1]) / c)
	print(M)
solve()


(n, m) = map(int, input().split())
w = list(map(int, input().split()))
ans = 0.0
for i in range(m):
	(u, v, c) = map(int, input().split())
	ans = max(ans, round((w[u - 1] + w[v - 1]) / c, 9))
print(ans)


import sys
input = sys.stdin.readline
from math import log2, log, ceil

def swaparr(arr, a, b):
	temp = arr[a]
	arr[a] = arr[b]
	arr[b] = temp

def gcd(a, b):
	if a == 0:
		return b
	return gcd(b % a, a)

def nCr(n, k):
	if k > n - k:
		k = n - k
	res = 1
	for i in range(k):
		res = res * (n - i)
		res = res / (i + 1)
	return res

def upper_bound(a, x, lo=0):
	hi = len(a)
	while lo < hi:
		mid = (lo + hi) // 2
		if a[mid] < x:
			lo = mid + 1
		else:
			hi = mid
	return lo

def primefs(n):
	primes = {}
	while n % 2 == 0:
		primes[2] = primes.get(2, 0) + 1
		n = n // 2
	for i in range(3, int(n ** 0.5) + 2, 2):
		while n % i == 0:
			primes[i] = primes.get(i, 0) + 1
			n = n // i
	if n > 2:
		primes[n] = primes.get(n, 0) + 1
	return primes

def power(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def swap(a, b):
	temp = a
	a = b
	b = temp
	return (a, b)

def find(x, link):
	while x != link[x]:
		x = link[x]
	return x

def union(x, y, link, size):
	x = find(x, link)
	y = find(y, link)
	if size[x] < size[y]:
		(x, y) = swap(x, y)
	if x != y:
		size[x] += size[y]
		link[y] = x

def sieve(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	return prime
MAXN = int(1000000.0 + 5)
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def find_parent(parent, i):
	if parent[i] == -1:
		return i
	if parent[i] != -1:
		return find_parent(parent, parent[i])
from collections import Counter
(n, m) = map(int, input().split())
arr = list(map(int, input().split()))
ma = 0
for i in range(m):
	(u, v, c) = map(int, input().split())
	ma = max(ma, (arr[u - 1] + arr[v - 1]) / c)
print('%.15f' % ma)


(nodes, edges) = map(int, input().split())
nodesValues = list(map(int, input().split()))
density = 0
total = 0
for i in range(edges):
	(node1, node2, edgeValue) = map(int, input().split())
	total = (nodesValues[node2 - 1] + nodesValues[node1 - 1]) / edgeValue
	if total > density:
		density = total
print(density)


(n, m) = map(int, input().split())
nodes = list(map(int, input().split()))
max_density = 0
for i in range(m):
	(n1, n2, e) = map(int, input().split())
	val = (nodes[n1 - 1] + nodes[n2 - 1]) / e
	if val > max_density:
		max_density = val
max_density = '{:.16f}'.format(max_density)
if max_density[-1] >= '5':
	print(max_density[:-2], int(max_density[-2]) + 1, sep='')
else:
	print(max_density[:-1])


(n, m) = map(int, input().split())
nodes = list(map(int, input().split()))
highest = 0
for i in range(m):
	(a, b, e) = map(int, input().split())
	val = (nodes[a - 1] + nodes[b - 1]) / e
	if highest < val:
		highest = val
print('{0:.9f}'.format(highest))


import sys
from collections import defaultdict
import math
from heapq import *
import itertools
MAXNUM = math.inf
MINNUM = -1 * math.inf
ASCIILOWER = 97
ASCIIUPPER = 65
pq = []
entry_finder = {}
REMOVED = '<removed-task>'
counter = itertools.count()

def add_task(task, priority=0):
	if task in entry_finder:
		remove_task(task)
	count = next(counter)
	entry = [priority, count, task]
	entry_finder[task] = entry
	heappush(pq, entry)

def remove_task(task):
	entry = entry_finder.pop(task)
	entry[-1] = REMOVED

def pop_task():
	while pq:
		(priority, count, task) = heappop(pq)
		if task is not REMOVED:
			del entry_finder[task]
			return task
	raise KeyError('pop from an empty priority queue')

def getInt():
	return int(sys.stdin.readline().rstrip())

def getInts():
	return map(int, sys.stdin.readline().rstrip().split(' '))

def getString():
	return sys.stdin.readline().rstrip()

def printOutput(ans):
	sys.stdout.write('%.15f' % ans)

def findParent(a, parents):
	cur = a
	while parents[cur] != cur:
		cur = parents[cur]
	parents[a] = cur
	return cur

def union(a, b, parents):
	parents[b] = a

def solve(nodeList, edgeList, edgeHeap):
	parents = [i for i in range(nodeList)]
	minTreeEdges = []
	totalEdges = defaultdict(int)
	while edgeHeap:
		(eVal, n1, n2) = heappop(edgeHeap)
		n1Parent = findParent(n1, parents)
		n2Parent = findParent(n2, parents)
		if n1Parent != n2Parent:
			union(n1Parent, n2Parent, parents)
			totalEdges[n1] += 1
			totalEdges[n2] += 1
			add_task(n1, totalEdges[n1])
			add_task(n2, totalEdges[n2])
			minTreeEdgeList[n1] = (n2, eVal)
			minTreeEdgeList[n2] = (n1, eVal)

def readinput():
	heap = []
	(v, e) = getInts()
	nodes = [0] + list(getInts())
	mx = 0
	for i in range(e):
		(n1, n2, e) = getInts()
		mx = max(mx, (nodes[n1] + nodes[n2]) / e)
	printOutput(mx)
readinput()


[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())
x = [int(c) for c in input().split()]
ans = 0
for _ in range(m):
	(a, b, c) = map(int, input().split())
	ans = max(ans, (x[a - 1] + x[b - 1]) / c)
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
	if cur > x:
		x = cur
print('%0.15f' % x)


(nodes, edges) = map(int, input().split())
x = list(map(int, input().split()))
error = 0
for i in range(edges):
	(a, b, c) = map(int, input().split())
	error = max(error, (x[a - 1] + x[b - 1]) / c)
print(error)


def read(mode=2):
	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='')
(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)


import sys
f = sys.stdin
(n, m) = map(int, f.readline().strip().split())
v = [int(u) for u in f.readline().strip().split()]
d = [{} for u in range(n)]
for i in range(m):
	(xi, yi, ei) = map(int, f.readline().strip().split())
	d[yi - 1][xi - 1] = ei
	d[xi - 1][yi - 1] = ei

def ff(i, s):
	for k in d[i]:
		if rt[k] == 0:
			rt[k] = s
			dlist[k] = 1
			ff(k, s)
s = 0
rt = [0 for u in range(n)]
glist = []
for i in range(n):
	if rt[i] == 0:
		s += 1
		dlist = {}
		rt[i] = s
		dlist[i] = 1
		ff(i, s)
		glist.append(dlist)
roMax = 0.0
t_ro = 0.0
ro = 0.0
for g in glist:
	if len(g) > 1:
		for gi in g:
			for u in d[gi]:
				if u in g:
					t_ro = (v[gi] + v[u]) / d[gi][u]
					if t_ro > ro:
						ro = t_ro
						graf = [gi, u]
print(ro)