Semiconductor Fabrication

Hanbyeol wants to donate a few semiconductors that he built himself to the juniors who will join the national collegiate programming contest club federation before he graduates. To make as many semiconductors as possible, he wants to minimize the cost of making one.

A semiconductor is a directed graph with $N$ vertices and $M$ edges. Vertices are numbered from $1$ to $N$, and vertex $i$ has potential energy $E_i$. Potential energies are real numbers, with $E_1=1.0$ and $E_N=-1.0$ fixed. Hanbyeol can choose the potential energies of the other vertices freely. Vertices $1$ and $N$ are special: no edge enters vertex $1$, and no edge leaves vertex $N$.

An edge $e=(u,v)$ can carry positive energy and negative energy from $u$ to $v$. Each edge has an energy transfer efficiency. If Hanbyeol sends positive energy $p_e(\ge 0)$ and negative energy $m_e(\le 0)$ through an edge with positive efficiency $a_e(\ge 0)$ and negative efficiency $b_e(\ge 0)$, the edge transfers $(a_e p_e + b_e m_e)$ energy. If the energy sent through edge $e=(u,v)$ does not satisfy $p_{(u,v)}+m_{(u,v)} \ge E_u - E_v$, the edge may overload and the semiconductor may break.

The cost of a semiconductor is the total energy transferred by all its edges. Help Hanbyeol choose the potential energies and the energy sent through each edge so that the semiconductor does not break and the cost is minimized.

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)$)

Each of the next $M$ lines contains four integers $u$, $v$, $a$, $b$, separated by spaces. This means there is an edge from vertex $u$ to vertex $v$ with positive efficiency $a$ and negative efficiency $b$. No duplicate edges are given. ($1\le u,v\le N$, $u\ne v$, $0\le a,b\le 10^9$)

Print the minimum cost of making one semiconductor. If the cost can be less than $-3\times 10^{-9}$, print HAPPY, the word for the feeling Hanbyeol has when he earns money every time he produces a semiconductor. Absolute or relative error up to $10^{-9}$ is accepted. No input has an answer that is at least $-3\times 10^{-9}$ and less than $-1\times 10^{-9}$.