Before graduating, Hanbyeol wants to donate some self-made semiconductors to the association of university programming clubs. To maximize the number of semiconductors produced, he wants to minimize the cost of producing a single semiconductor.
A semiconductor is in the form of a directed graph with $N$ vertices and $M$ edges. Each vertex is numbered from $1$ to $N$, and vertex $i$ has a potential energy $E_i$. The potential energy is a real number, with $E_1 = 1.0$ and $E_N = -1.0$ fixed, while the potential energies of the remaining vertices can be chosen arbitrarily by Hanbyeol. Additionally, since vertex $1$ and vertex $N$ are special, there are no incoming edges to vertex $1$ and no outgoing edges from vertex $N$.
An edge $e = (u, v)$ constituting the semiconductor can transmit positive energy and negative energy from vertex $u$ to $v$, respectively. Each edge of the semiconductor has a value called energy transmission efficiency. If Hanbyeol sends a positive energy of $p_e (\ge 0)$ and a negative energy of $m_e (\le 0)$ through an edge with positive energy transmission efficiency $a_e (\ge 0)$ and negative energy transmission efficiency $b_e (\ge 0)$, the amount of energy transmitted by the edge becomes $(a_e p_e + b_e m_e)$. However, if the energy sent to edge $e = (u, v)$ does not satisfy $p_{(u,v)} + m_{(u,v)} \ge E_u - E_v$, the semiconductor may break down due to overload.
The production cost of a semiconductor is equal to the sum of the energy transmitted by each edge constituting the semiconductor. Help Hanbyeol, who wants to do a good deed, by appropriately adjusting the potential energy of each vertex and the amount of energy sent to each edge so that the semiconductor does not break down and the production cost is minimized.
Input
The first line contains the number of vertices $N$ and the number of edges $M$ separated by a space. ($3 \le N \le 500$; $1 \le M \le N(N - 1)$)
From the second line, $M$ lines follow, each containing information about an edge constituting the semiconductor as $4$ integers $u, v, a, b$ separated by spaces. This means there is an edge from vertex $u$ to vertex $v$ with positive energy transmission efficiency $a$ and negative energy transmission efficiency $b$. No input with duplicate edges is given. ($1 \le u, v \le N$; $u \neq v$; $0 \le a, b \le 10^9$)
Output
Output the minimum production cost of one semiconductor. However, if the production cost can become less than $-3 \times 10^{-9}$, output "HAPPY", a word expressing Hanbyeol's mood when he can earn money every time he produces a semiconductor. Absolute/relative errors up to $10^{-9}$ are allowed, and inputs where the answer is between $-3 \times 10^{-9}$ and $-1 \times 10^{-9}$ will not be given.
Examples
Input 1
3 2 1 2 4 2 2 3 2 1
Output 1
4.00
Input 2
3 2 1 2 2 4 2 3 1 2
Output 2
HAPPY
Note
In Example 1, if we set $p_{1,2} = 0.0, m_{1,2} = 0.0, p_{2,3} = 2.0, m_{2,3} = 0.0, E_2 = 1.0$, then $p_{1,2} + m_{1,2} = 0.0 \ge E_1 - E_2 = 0.0$ and $p_{2,3} + m_{2,3} = 2.0 \ge E_2 - E_3 = 2.0$ are satisfied. The cost becomes $4.0$, and the cost cannot be reduced further.
In Example 2, if we set $p_{1,2} = 3.0, m_{1,2} = -2.0, p_{2,3} = 3.0, m_{2,3} = -2.0, E_2 = 0.0$, then $p_{1,2} + m_{1,2} = 1.0 \ge E_1 - E_2 = 1.0$ and $p_{2,3} + m_{2,3} = 1.0 \ge E_2 - E_3 = 1.0$ are satisfied. The cost becomes $-3.0$, and since the production cost can be negative, Hanbyeol becomes very happy.