A clash of galaxies is coming! A galaxy ruled by the mysterious MdI is trying to annex our milky way, but the galactical government has plans to turn things round. Our intelligence agency has infiltrated the enemy’s headquarter and gained surprising intelligence. The enemy is moving its units around according to a fixed scheme: for each fort a fraction of the units is moved to other forts in each time unit (the time of the flight is negligible). Now the government has fixed a time when to attack. Your order is to compute the weak points. But as the enemy's galaxy is far, far away it takes one time unit to fly there. Furthermore, we are also certain that the MdI will recognize our target and immediately start all ships which can reach our attacking point (via one link, regardless of its direction). The spy informed you that these strengths are only statistical values, i.e. some sort of indicator as float. \InputFile The first line of the input contains the number of test cases (\textbf{1} ≤ \textbf{T} ≤ \textbf{10}). Each test case starts with one line containing three integers stating the number of enemy forts \textbf{N} (\textbf{1} ≤ \textbf{N} ≤ \textbf{100}), the number of links \textbf{l} (\textbf{0} ≤ \textbf{l} ≤ \textbf{(N-1)^2}) and the time from now when to attack \textbf{t} (\textbf{0} ≤ \textbf{t} ≤ \textbf{5000}). The second line contains \textbf{N} doubles \textbf{u_i} (\textbf{0} ≤ \textbf{u_i} ≤ \textbf{1000}) specifying the strength of the stationed troops at each fort followed by \textbf{l} lines containing the links. Each link is described by two integers \textbf{s_j} (\textbf{0} ≤ \textbf{s_j} < \textbf{N}), \textbf{t_j} (\textbf{0} ≤ \textbf{t_j} < \textbf{N}) describing the source and the target of the link and one double \textbf{p_j} (\textbf{0} < \textbf{p_j} ≤ \textbf{1}), the fraction of units transferred from \textbf{s_j} to \textbf{t_j} in each time unit. \OutputFile Print the lowest indicator of the enemy galaxy with an absolute or relative error less than \textbf{10^\{-6\}}. \includegraphics{https://static.e-olymp.com/content/09/091a7ef84b2c218557cb6ee51756371303082a01.jpg} \textit{\textbf{Figure 1}} -- The statistical strengths of the first sample before and after the first time step. \includegraphics{https://static.e-olymp.com/content/37/372555c99cf2f694092976a81d35cb21e7c6ad8c.jpg} \textit{\textbf{Figure 2}} -- Strength of the forces to face at each fort. Note that links are used in both directions.