mst

Fie $G$ un graf neorientat conex. Fiecare muchie $e$ are la momentul $t$ un cost dat de o funcţie polinomială de gradul al doilea $fe(t) = a_e \cdot t^2 + b_e \cdot t + c \cdot e$.

Cerinţă

Găsiţi timpul $t$ la care costul arborelui de acoperire minim al lui $G$ este cât mai mic posibil, precum şi acest cost.

Date de intrare

Pe prima linie a fişierului de intrare mst.in se găsesc două numere naturale $N$ şi $M$, separate printr-un spaţiu, reprezentând numărul nodurilor din graf, respectiv, numărul muchiilor. Pe linia $i + 1$ se găsesc numerele $u_i \ v_i \ a_i \ b_i \ c_i$, separate prin câte un spaţiu, unde $u_i$ şi $v_i$ sunt capetele muchiei, iar $a_i, b_i, c_i$ coeficienţii funcţiei polinomiale.

Date de ieșire

Pe prima linie a fişierului de ieşire mst.out se vor scrie două numere reale cu exact $6$ zecimale, primul fiind timpul căutat iar al doilea costul arborelui de acoperire minim în acel moment.

Restricții și precizări

• $2 \leq N \leq 100$
• $1 \leq M \leq 100$
• $0 \leq u_i, v_i < N$, oricare $1 \leq i \leq M$.
• Coeficienţii $a_i, b_i, c_i$ sunt numere întregi a căror valoare absolută nu depăşeşte 10^6, oricare $1 \leq i \leq M$.
• Coeficientul $a_i > 0$, oricare $1 \leq i \leq M$.
• Timpul $t$ poate fi orice valoare de pe axa reală.
• Funcţiile asociate muchiilor sunt distincte două câte două.
• Rezultatele vor fi considerate corecte dacă nu au o eroare mai mare de $10^{-6}$ (a şasea zecimală poate să difere cu cel mult o unitate).

Exemplu

mst.in

3 3
0 1 1 -2 1
1 2 1 -2 5
0 2 1 -8 16

mst.out

1.000000 4.000000

Explicație

Funcţiile asociate muchiilor sunt:

• $f(0,1)(t) = t^2 - 2t + 1$,
• $f(1,2)(t) = t^2 - 2t + 5$,
• $f(2,0)(t) = t^2 - 8t + 16$.
  Minimele funcţiilor $f(0,1)$, $f(1,2)$ se ating la momentul $t = 1$ iar suma lor este $4$.