Maximizing Fun Ratio on City Tour

Farmer John is taking his cows on a tour of the big city! The city consists of L landmarks (numbered 1 through L) and P directed cowpaths. Each landmark i has an associated fun value \(F_i\) and each cowpath from landmark \(u\) to landmark \(v\) takes a time \(T_{uv}\) to traverse.

The cows choose a starting landmark and then walk along a sequence of cowpaths forming a cycle (returning to the starting landmark) while ensuring that at least two distinct landmarks are visited. Note that the fun value of a landmark is only counted the first time it is visited on the tour. For a simple cycle, every landmark is visited exactly once so the total fun value is \(\sum_{v\in C}F_v\) and the total time required is \(\sum_{(u,v)\in C}T_{uv}\). The objective is to maximize the average fun per unit time. In other words, find a cycle \(C\) (with at least 2 landmarks) that maximizes the ratio

[ R = \frac{\sum_{v\in C} F_v}{\sum_{(u,v)\in C} T_{uv}} ]

If no cycle exists then the maximum fun ratio is defined to be 0.

Hint: This is a maximum cycle ratio problem. One common approach is to use parametric search (via binary search) that determines the largest \(r\) for which there exists a cycle satisfying \[ \sum_{(u,v)\in C}(F_u - r \cdot T_{uv}) \ge 0. \]

inputFormat

The first line contains two integers \(L\) and \(P\) (2 ≤ L ≤ 1000, 2 ≤ P ≤ 5000), representing the number of landmarks and cowpaths respectively.

The second line contains \(L\) integers: \(F_1, F_2, \dots, F_L\) (1 ≤ \(F_i\) ≤ 1000), where \(F_i\) is the fun value for landmark \(i\).

Each of the next \(P\) lines contains three integers \(u\), \(v\), and \(T\) (1 ≤ \(T\) ≤ 1000) indicating there is a directed cowpath from landmark \(u\) to landmark \(v\) with travel time \(T\).

outputFormat

Output one line containing a floating‐point number representing the maximum achievable fun per unit time. The answer will be accepted if it has an absolute or relative error of at most 10⁻⁶.

If no cycle exists then output 0.

sample

3 3
5 10 5
1 2 3
2 3 2
3 1 4

2.222222222