Avant d'obtenir son diplôme, Hanbyeol souhaite faire don de plusieurs semi-conducteurs qu'il a fabriqués lui-même à l'association des clubs de programmation universitaire. Afin de fabriquer autant de semi-conducteurs que possible, il cherche à minimiser le coût de fabrication d'un seul semi-conducteur.
Un semi-conducteur est représenté par un graphe orienté avec $N$ sommets et $M$ arêtes. Chaque sommet est numéroté de $1$ à $N$, et le sommet $i$ possède une énergie potentielle $E_i$. L'énergie potentielle est une valeur réelle, avec $E_1 = 1.0$ et $E_N = -1.0$ fixés, tandis que les énergies potentielles des autres sommets peuvent être choisies arbitrairement par Hanbyeol. De plus, comme les sommets $1$ et $N$ sont des sommets spéciaux, il n'existe aucune arête entrant dans le sommet $1$ ni aucune arête sortant du sommet $N$.
Chaque arête $e = (u, v)$ constituant le semi-conducteur peut transmettre de l'énergie positive et de l'énergie négative du sommet $u$ vers le sommet $v$. Chaque arête possède une valeur appelée efficacité de transfert d'énergie. Si Hanbyeol envoie une quantité d'énergie positive $p_e (\ge 0)$ et une quantité d'énergie négative $m_e (\le 0)$ à travers une arête ayant une efficacité de transfert d'énergie positive $a_e (\ge 0)$ et une efficacité de transfert d'énergie négative $b_e (\ge 0)$, la quantité d'énergie transmise par l'arête est $(a_e p_e + b_e m_e)$. Cependant, si l'énergie envoyée à l'arête $e = (u, v)$ ne satisfait pas la condition $p_e + m_e \ge E_u - E_v$, le semi-conducteur peut tomber en panne en raison d'une surcharge.
Le coût de fabrication du semi-conducteur est égal à la somme totale de l'énergie transmise par chaque arête constituant le semi-conducteur. Aidez Hanbyeol, qui souhaite faire une bonne action, à ajuster de manière appropriée l'énergie potentielle de chaque sommet et la quantité d'énergie envoyée à chaque arête afin que le semi-conducteur ne tombe pas en panne et que le coût de fabrication soit minimisé.
Entrée
La première ligne contient le nombre de sommets $N$ et le nombre d'arêtes $M$, séparés par un espace. ($3 \le N \le 500$; $1 \le M \le N(N - 1)$)
À partir de la deuxième ligne, les informations sur les $M$ arêtes composant le semi-conducteur sont données sur $M$ lignes, chacune contenant 4 entiers $u, v, a, b$ séparés par des espaces. Cela signifie qu'il existe une arête allant du sommet $u$ au sommet $v$ avec une efficacité de transfert d'énergie positive $a$ et une efficacité de transfert d'énergie négative $b$. Aucune entrée avec des arêtes multiples n'est fournie. ($1 \le u, v \le N; u \neq v; 0 \le a, b \le 10^9$)
Sortie
Affichez la valeur minimale du coût de fabrication d'un semi-conducteur. Cependant, si le coût de fabrication peut devenir inférieur à $-3 \times 10^{-9}$, affichez HAPPY, le mot exprimant l'humeur de Hanbyeol lorsqu'il peut gagner de l'argent à chaque production de semi-conducteur. Une erreur absolue/relative de $10^{-9}$ est tolérée, et aucune entrée où la réponse est comprise entre $-3 \times 10^{-9}$ et $-1 \times 10^{-9}$ ne sera fournie.
Exemples
Entrée 1
3 2 1 2 4 2 2 3 2 1
Sortie 1
4.00
Entrée 2
3 2 1 2 2 4 2 3 1 2
Sortie 2
HAPPY
Remarque
Dans l'exemple 1, si l'on définit $p_{1,2} = 0.0, m_{1,2} = 0.0, p_{2,3} = 2.0, m_{2,3} = 0.0, E_2 = 1.0$, alors $p_{1,2} + m_{1,2} = 0.0 \ge E_1 - E_2 = 0.0$ et $p_{2,3} + m_{2,3} = 2.0 \ge E_2 - E_3 = 2.0$ sont satisfaites. Le coût est de $4.0$, et il n'est pas possible de réduire le coût davantage.
Dans l'exemple 2, si l'on définit $p_{1,2} = 3.0, m_{1,2} = -2.0, p_{2,3} = 3.0, m_{2,3} = -2.0, E_2 = 0.0$, alors $p_{1,2} + m_{1,2} = 1.0 \ge E_1 - E_2 = 1.0$ et $p_{2,3} + m_{2,3} = 1.0 \ge E_2 - E_3 = 1.0$ sont satisfaites. Le coût est de $-3.0$, et comme le coût de fabrication peut être négatif, Hanbyeol devient très heureux.