ハンビョルは卒業前に、全国大学生プログラミング大会サークル連合に入ってくる後輩たちのために、自作の半導体をいくつか寄付しようとしている。このとき、半導体を最大限多く作るために、半導体1つを作るのにかかる費用を最小化しようとする。

半導体は頂点が $N$ 個、辺が $M$ 個の有向グラフの形をしている。各頂点には1番から $N$ 番までの番号が付けられており、$i$ 番頂点はポテンシャルエネルギー $E_i$ を持っている。ポテンシャルエネルギーは実数値であり、$E_1 = 1.0$、$E_N = -1.0$ に固定されており、残りの頂点のポテンシャルエネルギーはハンビョルが任意に決めることができる。さらに、1番頂点と $N$ 番頂点は特殊な頂点であるため、1番頂点に入ってくる辺と $N$ 番頂点から出ていく辺は存在しない。

半導体を構成している辺 $e = (u, v)$ は、頂点 $u$ から $v$ へ正のエネルギーと負のエネルギーをそれぞれ伝達できる。半導体の各辺はエネルギー伝達効率という値を持っている。もしハンビョルが正のエネルギー伝達効率が $a_e (\ge 0)$、負のエネルギー伝達効率が $b_e (\ge 0)$ である辺に、正のエネルギーを正の実数 $p_e (\ge 0)$、負のエネルギーを負の実数 $m_e (\le 0)$ だけ送るならば、辺が伝達するエネルギーの量は $(a_e p_e + b_e m_e)$ となる。ただし、辺 $e = (u, v)$ に送るエネルギーが $p_{(u,v)} + m_{(u,v)} \ge E_u - E_v$ を満たさない場合、過負荷により半導体が故障する可能性がある。

半導体の製作費用は、半導体を構成する各辺が伝達するエネルギーの総和と等しい。良いことをしようとするハンビョルを助け、半導体の各頂点のポテンシャルエネルギーと各辺に送るエネルギーの量を適切に調整し、半導体が故障しないようにしながら製作費用が最小になるようにしてみよう。

入力

最初の行には頂点数 $N$ と辺の数 $M$ が空白で区切られて与えられる。$(3 \le N \le 500; 1 \le M \le N(N - 1))$

2番目の行から合計 $M$ 行にわたって、半導体を構成する辺の情報が空白で区切られた4つの整数 $u, v, a, b$ で与えられる。これは $u$ 番目の頂点から $v$ 番目の頂点に向かい、正のエネルギー伝達効率が $a$、負のエネルギー伝達効率が $b$ である辺が存在することを意味する。重複する辺がある入力は与えられない。$(1 \le u, v \le N; u \neq v; 0 \le a, b \le 10^9)$

出力

半導体1つの製作費用の最小値を出力せよ。ただし、製作費用が $-3 \times 10^{-9}$ より小さくなる場合、半導体を生産するたびに利益を得られるハンビョルの気分を表す単語である HAPPY を出力せよ。絶対誤差または相対誤差は $10^{-9}$ まで許容され、答えが $-3 \times 10^{-9}$ 以上 $-1 \times 10^{-9}$ 未満である入力は与えられない。

入出力例

入力 1

3 2
1 2 4 2
2 3 2 1

出力 1

4.00

入力 2

3 2
1 2 2 4
2 3 1 2

出力 2

HAPPY

注記

例1は $p_{1,2} = 0.0, m_{1,2} = 0.0, p_{2,3} = 2.0, m_{2,3} = 0.0, E_2 = 1.0$ と指定すれば、$p_{1,2} + m_{1,2} = 0.0 \ge E_1 - E_2 = 0.0$、$p_{2,3} + m_{2,3} = 2.0 \ge E_2 - E_3 = 2.0$ を満たすことになる。費用は $4.0$ となり、これ以上費用を減らすことはできない。

例2は $p_{1,2} = 3.0, m_{1,2} = -2.0, p_{2,3} = 3.0, m_{2,3} = -2.0, E_2 = 0.0$ と指定すれば、$p_{1,2} + m_{1,2} = 1.0 \ge E_1 - E_2 = 1.0$、$p_{2,3} + m_{2,3} = 1.0 \ge E_2 - E_3 = 1.0$ を満たすことになる。費用は $-3.0$ となり、製作費用が負になり得るため、ハンビョルは非常に幸せになる。