Hanbyeol przed ukończeniem studiów chce podarować młodszym kolegom z koła naukowego własnoręcznie wykonane półprzewodniki. Aby wyprodukować ich jak najwięcej, chce zminimalizować koszt wytworzenia pojedynczego półprzewodnika.
Półprzewodnik ma postać grafu skierowanego z $N$ wierzchołkami i $M$ krawędziami. Każdy wierzchołek jest ponumerowany od $1$ do $N$, a wierzchołek $i$ posiada energię potencjalną $E_i$. Energia potencjalna jest wartością rzeczywistą, przy czym $E_1 = 1.0$ oraz $E_N = -1.0$ są ustalone, a energie potencjalne pozostałych wierzchołków Hanbyeol może ustalić dowolnie. Ponadto, wierzchołki $1$ i $N$ są specjalne: nie istnieją krawędzie wchodzące do wierzchołka $1$ ani wychodzące z wierzchołka $N$.
Krawędź $e = (u, v)$ tworząca półprzewodnik może przesyłać energię dodatnią oraz ujemną z wierzchołka $u$ do $v$. Każda krawędź półprzewodnika posiada wartość zwaną efektywnością przesyłu energii. Jeśli Hanbyeol prześle przez krawędź o efektywności przesyłu energii dodatniej $a_e (\ge 0)$ oraz efektywności przesyłu energii ujemnej $b_e (\ge 0)$ odpowiednio energię dodatnią $p_e (\ge 0)$ oraz energię ujemną $m_e (\le 0)$, to ilość energii przesyłanej przez krawędź wyniesie $(a_e p_e + b_e m_e)$. Jednakże, jeśli przesyłana przez krawędź $e = (u, v)$ energia nie spełnia warunku $p_e + m_e \ge E_u - E_v$, półprzewodnik może ulec awarii z powodu przeciążenia.
Koszt produkcji półprzewodnika jest równy sumie energii przesyłanych przez każdą z krawędzi tworzących półprzewodnik. Pomóż Hanbyeolowi, który chce zrobić dobry uczynek, odpowiednio dostosować energię potencjalną każdego wierzchołka oraz ilość energii przesyłanej przez każdą krawędź tak, aby półprzewodnik nie uległ awarii, a koszt produkcji był minimalny.
Wejście
W pierwszej linii podano liczbę wierzchołków $N$ oraz liczbę krawędzi $M$ rozdzielone spacją. ($3 \le N \le 500$; $1 \le M \le N(N - 1)$)
Od drugiej linii, przez łącznie $M$ linii, podane są informacje o krawędziach tworzących półprzewodnik w postaci 4 liczb całkowitych $u, v, a, b$ rozdzielonych spacjami. Oznacza to, że istnieje krawędź skierowana z wierzchołka $u$ do wierzchołka $v$, której efektywność przesyłu energii dodatniej wynosi $a$, a efektywność przesyłu energii ujemnej wynosi $b$. Dane wejściowe nie zawierają krawędzi wielokrotnych. ($1 \le u, v \le N; u \neq v; 0 \le a, b \le 10^9$)
Wyjście
Wypisz minimalny koszt produkcji jednego półprzewodnika. Jeśli jednak koszt produkcji może stać się mniejszy niż $-3 \times 10^{-9}$, wypisz słowo HAPPY, wyrażające nastrój Hanbyeola, który może zarabiać pieniądze przy każdej produkcji półprzewodnika. Dopuszczalny błąd bezwzględny/względny wynosi $10^{-9}$. Dane wejściowe, dla których odpowiedź wynosi od $-3 \times 10^{-9}$ do $-1 \times 10^{-9}$ (wyłącznie), nie wystąpią.
Przykład
Wejście 1
3 2 1 2 4 2 2 3 2 1
Wyjście 1
4.00
Wejście 2
3 2 1 2 2 4 2 3 1 2
Wyjście 2
HAPPY
Uwagi
W przykładzie 1, jeśli przyjmiemy $p_{1,2} = 0.0, m_{1,2} = 0.0, p_{2,3} = 2.0, m_{2,3} = 0.0, E_2 = 1.0$, to spełnione zostaną warunki $p_{1,2} + m_{1,2} = 0.0 \ge E_1 - E_2 = 0.0$ oraz $p_{2,3} + m_{2,3} = 2.0 \ge E_2 - E_3 = 2.0$. Koszt wynosi $4.0$ i nie można go bardziej zredukować.
W przykładzie 2, jeśli przyjmiemy $p_{1,2} = 3.0, m_{1,2} = -2.0, p_{2,3} = 3.0, m_{2,3} = -2.0, E_2 = 0.0$, to spełnione zostaną warunki $p_{1,2} + m_{1,2} = 1.0 \ge E_1 - E_2 = 1.0$ oraz $p_{2,3} + m_{2,3} = 1.0 \ge E_2 - E_3 = 1.0$. Koszt wynosi $-3.0$, a ponieważ koszt produkcji może być ujemny, Hanbyeol staje się bardzo szczęśliwy.