Hanbyeol muốn quyên góp một số linh kiện bán dẫn mà cậu ấy tự tay chế tạo cho liên đoàn các câu lạc bộ lập trình sinh viên trên toàn quốc trước khi tốt nghiệp. Để có thể chế tạo được nhiều linh kiện nhất có thể, cậu ấy muốn tối thiểu hóa chi phí sản xuất cho mỗi linh kiện.

Linh kiện bán dẫn có dạng một đồ thị có hướng với $N$ đỉnh và $M$ cạnh. Mỗi đỉnh được đánh số từ $1$ đến $N$, và đỉnh $i$ có một giá trị thế năng $E_i$. Thế năng là một giá trị thực, với $E_1 = 1.0$ và $E_N = -1.0$ được cố định, trong khi thế năng của các đỉnh còn lại có thể được Hanbyeol tùy ý thiết lập. Ngoài ra, vì đỉnh $1$ và đỉnh $N$ là các đỉnh đặc biệt, không có cạnh nào đi vào đỉnh $1$ và không có cạnh nào đi ra từ đỉnh $N$.

Mỗi cạnh $e = (u, v)$ cấu tạo nên linh kiện bán dẫn có thể truyền cả năng lượng dương và năng lượng âm từ đỉnh $u$ sang đỉnh $v$. Mỗi cạnh của linh kiện có một giá trị gọi là hiệu suất truyền năng lượng. Nếu Hanbyeol gửi một lượng năng lượng dương $p_e (\ge 0)$ và một lượng năng lượng âm $m_e (\le 0)$ qua một cạnh có hiệu suất truyền năng lượng dương là $a_e (\ge 0)$ và hiệu suất truyền năng lượng âm là $b_e (\ge 0)$, thì lượng năng lượng mà cạnh đó truyền đi sẽ là $(a_e p_e + b_e m_e)$. Tuy nhiên, nếu năng lượng gửi qua cạnh $e = (u, v)$ không thỏa mãn điều kiện $p_{(u,v)} + m_{(u,v)} \ge E_u - E_v$, linh kiện có thể bị hỏng do quá tải.

Chi phí sản xuất linh kiện bằng tổng năng lượng truyền đi qua mỗi cạnh cấu tạo nên linh kiện đó. Hãy giúp Hanbyeol, người đang muốn làm việc tốt, bằng cách điều chỉnh thế năng của mỗi đỉnh và lượng năng lượng gửi qua mỗi cạnh một cách hợp lý để linh kiện không bị hỏng và chi phí sản xuất là nhỏ nhất.

Dữ liệu vào

Dòng đầu tiên chứa số lượng đỉnh $N$ và số lượng cạnh $M$ được phân cách bởi khoảng trắng ($3 \le N \le 500$; $1 \le M \le N(N - 1)$).

Từ dòng thứ hai trở đi, trong tổng số $M$ dòng, thông tin về các cạnh cấu tạo nên linh kiện được cung cấp dưới dạng 4 số nguyên $u, v, a, b$ phân cách bởi khoảng trắng. Điều này có nghĩa là có một cạnh hướng từ đỉnh $u$ đến đỉnh $v$ với hiệu suất truyền năng lượng dương là $a$ và hiệu suất truyền năng lượng âm là $b$. Không có dữ liệu về các cạnh trùng lặp. ($1 \le u, v \le N; u \neq v; 0 \le a, b \le 10^9$)

Dữ liệu ra

Hãy in ra giá trị nhỏ nhất của chi phí sản xuất một linh kiện. Tuy nhiên, nếu chi phí sản xuất có thể nhỏ hơn $-3 \times 10^{-9}$, hãy in ra từ "HAPPY", từ thể hiện tâm trạng của Hanbyeol khi cậu ấy có thể kiếm được tiền mỗi khi sản xuất linh kiện. Sai số tuyệt đối/tương đối cho phép là $10^{-9}$, và các trường hợp có đáp án trong khoảng từ $-3 \times 10^{-9}$ đến $-1 \times 10^{-9}$ sẽ không xuất hiện trong dữ liệu vào.

Ví dụ

Ví dụ 1

3 2
1 2 4 2
2 3 2 1

Ví dụ 1

4.00

Ví dụ 2

3 2
1 2 2 4
2 3 1 2

Ví dụ 2

HAPPY

Ghi chú

Ở ví dụ 1, nếu ta đặt $p_{1,2} = 0.0, m_{1,2} = 0.0, p_{2,3} = 2.0, m_{2,3} = 0.0, E_2 = 1.0$, thì các điều kiện $p_{1,2} + m_{1,2} = 0.0 \ge E_1 - E_2 = 0.0$ và $p_{2,3} + m_{2,3} = 2.0 \ge E_2 - E_3 = 2.0$ được thỏa mãn. Chi phí là $4.0$ và không thể giảm chi phí xuống thấp hơn mức này.

Ở ví dụ 2, nếu ta đặt $p_{1,2} = 3.0, m_{1,2} = -2.0, p_{2,3} = 3.0, m_{2,3} = -2.0, E_2 = 0.0$, thì các điều kiện $p_{1,2} + m_{1,2} = 1.0 \ge E_1 - E_2 = 1.0$ và $p_{2,3} + m_{2,3} = 1.0 \ge E_2 - E_3 = 1.0$ được thỏa mãn. Chi phí là $-3.0$, và vì chi phí sản xuất có thể trở thành số âm, Hanbyeol trở nên rất hạnh phúc.