Hanbyeol 打算在畢業前為即將加入全國大學生程式設計競賽社團聯會的學弟妹們捐贈一些他親手製作的半導體。為了能製作出盡可能多的半導體，他希望將製作一個半導體的成本降至最低。

半導體的形式為一個具有 $N$ 個頂點與 $M$ 條邊的有向圖。每個頂點標號為 $1$ 到 $N$，第 $i$ 個頂點具有勢能 $E_i$。勢能為實數，其中 $E_1 = 1.0$，$E_N = -1.0$ 為固定值，其餘頂點的勢能可由 Hanbyeol 任意設定。此外，由於 $1$ 號頂點與 $N$ 號頂點為特殊頂點，不存在進入 $1$ 號頂點的邊，也不存在從 $N$ 號頂點發出的邊。

構成半導體的邊 $e = (u, v)$ 可以分別從頂點 $u$ 傳遞正能量與負能量至 $v$。半導體的每條邊都有一個能量傳遞效率值。若 Hanbyeol 在正能量傳遞效率為 $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$，則半導體可能會因過載而損壞。

半導體的製作成本等於構成半導體的各條邊所傳遞能量的總和。請幫助想要做善事的 Hanbyeol，透過適當調整半導體各頂點的勢能以及各條邊傳送的能量，在半導體不損壞的前提下，使製作成本達到最小。

輸入格式

第一行包含頂點數量 $N$ 與邊數量 $M$，以空格分隔。($3 \le N \le 500$; $1 \le M \le N(N - 1)$)

從第二行開始，共 $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$)

輸出格式

輸出製作一個半導體的最小成本。若製作成本可以小於 $-3 \times 10^{-9}$，則輸出單字 HAPPY，代表 Hanbyeol 每次生產半導體都能獲利時的心情。答案允許 $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$，由於製作成本可能為負數，Hanbyeol 會感到非常快樂。