Amplification System Optimization

An amplification system consists of n routers and m amplifiers. The microphone is connected to router 1 and the speaker is connected to router n.

Each amplifier connects two routers (an input router and an output router) and has a gain coefficient \(w_i\). Each router has a maximum bandwidth (or capacity) \(p_i\). The microphone produces a signal with power 1. When the signal passes through an amplifier, its power is multiplied by the amplifier's gain coefficient. However, to avoid burning the router, the signal power at any router must not exceed the router's capacity \(p_i\). Note that the signal is allowed to pass through the same router or amplifier multiple times.

The objective is to configure the system so as to maximize the signal power at router n (the speaker), while ensuring that at every router the signal power does not exceed its capacity. Compute the maximum possible signal power at router n.

Note: If router n is unreachable, output 0.

inputFormat

The first line contains two integers n and m (\(2 \leq n \leq 10^5\), \(1 \leq m \leq 10^5\)) — the number of routers and amplifiers.

The second line contains n real numbers \(p_1, p_2, \dots, p_n\) where \(p_i\) is the maximum allowed signal power for router i. It is guaranteed that \(p_1 \geq 1\) (so that the microphone's signal does not burn router 1).

Each of the next m lines contains two integers and one real number: u v w, representing an amplifier connecting router u (input) to router v (output) with gain coefficient \(w\). (\(1 \le u, v \le n\); \(w > 0\)).

outputFormat

Output a single real number — the maximum achievable signal power at router n under the condition that at every router, the signal power does not exceed its capacity. If router n is unreachable, output 0.

sample

3 3
10 5 20
1 2 3
2 3 6
1 3 2

18