Timing

A collision between galaxies is coming. The galaxy ruled by MdI wants to annex ours by force. Our intelligence service broke into the enemy headquarters and came back with the whole troop movement plan.

The enemy troops are spread over $N$ fortresses. Let $u_i$ be the power statistic of the troops in fortress $i$. The plan moves troops along links. A link $(s, d, p)$ means that every hour a fraction $p$ of the troops in fortress $s$ crosses over to fortress $d$. The travel time between fortresses is ignored.

All moves inside one hour happen at the same time and use the values from the start of that hour, so after one hour fortress $i$ holds

$u_i' = u_i - \sum_{(s, d, p) \,:\, s = i} p \cdot u_i + \sum_{(s, d, p) \,:\, d = i} p \cdot u_s$

The government picked the hour $t$ at which the attack starts, so the enemy follows the plan for $t$ hours. The enemy galaxy is far away and our fleet needs one hour to get there. MdI notices the target the moment the fleet leaves and immediately moves every soldier who can reach it. Direction stops mattering during that hour, so a fortress joined to the target fortress $v$ by a link sends all of its troops to $v$ and keeps none.

The power statistic $g_v$ gathered at fortress $v$ when the fleet arrives is therefore $u_v$ after $t$ hours plus the value of every fortress joined to $v$ by a link. Writing $A(v)$ for the set of fortresses joined to $v$ by at least one link, with $v$ itself left out,

$g_v = u_v + \sum_{w \in A(v)} u_w$

Link direction is ignored here, and a fortress counts once even when several links join it to $v$.

Find the weakest point of the enemy galaxy, that is the smallest $g_v$ over all fortresses.

The first line has the number of test cases $T$ ($1 \le T \le 10$).

The first line of each test case has the number of enemy fortresses $N$ ($1 \le N \le 100$), the number of links $l$ ($0 \le l \le (N-1)^2$), and the hour of the attack $t$ ($0 \le t \le 5000$). The second line has $N$ real numbers $u_0, u_1, \dots, u_{N-1}$ ($0 \le u_i \le 1000$), where $u_i$ is the power statistic of the troops in fortress $i$.

Each of the next $l$ lines describes one link with an integer $s_j$ ($0 \le s_j < N$), an integer $d_j$ ($0 \le d_j < N$), and a real number $p_j$ ($0 < p_j \le 1$), meaning that every hour a fraction $p_j$ of the troops in fortress $s_j$ moves to fortress $d_j$. The same pair may appear more than once, and a link with $s_j = d_j$ is possible. The ratios on the links leaving one fortress add up to at most 1.

For each test case print, on its own line, the value of the weakest point of the enemy galaxy, that is the smallest power statistic that can gather in a single fortress by the time the fleet arrives.

Round the value at the seventh digit after the decimal point and print exactly six digits after the decimal point. If the answer is $305$, print 305.000000. Every input keeps the answer far away from a rounding boundary, so the rounding direction is never in doubt.

Every link works both ways at the moment the attack starts. A fortress joined to the target by a link sends all of its troops there, whichever way the link points.

The moves during the $t$ hours before that follow the plan and keep their direction. Only the last hour ignores it.