== include(page="template/taskheader" task_id="ghoberdist") ==

Dupa ce GhoberBoss a ghober-autizat la ghober-concurs va da aceasta ghober-problema. Ai un graf conex cu N noduri si M muchii ponderate. Costul unui drum este egal cu costul maxim al unei muchii de pe acesta.
Definim functia f(x, y) = costul minim al unui drum de la x la y. Se dau Q query-uri de forma: $K a{~1~} a{~2~} ... a{~k~}$. Se cere pentru fiecare query suma de f(ai, aj) pentru fiecare pereche (i, j) unde $1 &le i < j &le k&.

bq. Esti Ghober-prost sa mor eu
Friedrich Nietzsche
 
 
Dupa ce GhoberBoss a ghober-autizat la ghober-concurs va da aceasta ghober-problema ca ghober-razbunare:
 
 Ai un graf conex cu $N$ noduri si $M$ muchii ponderate. Costul unui drum este egal cu costul maxim al unei muchii de pe acesta.
Definim functia $f(x, y)$ = costul minim al unui drum de la $x$ la $y$. Se dau $Q$ query-uri de forma: $K a{~1~} a{~2~} ... a{~k~}$. Se cere pentru fiecare query suma de $f(a{~i~}, a{~j~})$ pentru fiecare pereche $(i, j)$ unde $1 &le; i < j &le; k$.

h2. Date de intrare

Pe prima linie a fişierului de intrare $ghoberdist.in$ se afla numerele $N$ si $M$. Pe urmatoarele $M$ linii se alfa 3 numere $x y z$ care inseamna ca exista o muchie intre nodurile $x$ si $y$ cu costul $z$. Pe urmatoarea linie se afla $Q$, iar pe urmatoarele Q linii se afla query-urile in formatul $K a{~1~} a{~2~} ... a{~k~}$.

Pe prima linie a fişierului de intrare $ghoberdist.in$ se afla numerele $N$ si $M$. Pe urmatoarele $M$ linii se alfa 3 numere $x y z$ care inseamna ca exista o muchie intre nodurile $x$ si $y$ cu costul $z$. Pe urmatoarea linie se afla $Q$, iar pe urmatoarele $Q$ linii se afla query-urile in formatul $K a{~1~} a{~2~} ... a{~k~}$.

h2. Date de ieşire

h2. Restricţii

table(restrictii). |. # |. Punctaj |_. Restricţii |
| $1$ | $8$ | $1 ≤ N, Q, ≤ $ |
| $2$ | $20$ | $31 ≤ N ≤ 120$ |
| $3$ | $70$ | $121 ≤ N ≤ 1 000$ |

* Fie $S$ = suma tuturor $K$-urilor de la intrare.
* Costul fiecarei muchii este mai mic sau egal decat $1 000 000$
* Raspunsul se incadreaza intr-un tip de date cu 64 de biti cu semn
* Pentru orice subtask, daca nu este precizat, $K ≥ 2$, si implicit $2 * Q ≤ S$
 
 
table(restrictii). |_. # |_. Punctaj |_. Restricţii |
| $1$ | $8$ | $1 ≤ N, M, S ≤ 1 000$ |
| $2$ | $23$ | $1 ≤ N ≤ 100 000, 1 ≤ S, M ≤ 200 000, K = 2$|
| $3$ | $19$ | $1 ≤ N ≤ 100 000, M = N-1, 1 ≤ S ≤ 200 000, Graful este un lant$|
| $4$ | $16$ | $1 ≤ N ≤ 100 000, 1 ≤ S, M ≤ 200 000$, $1 ≤ Q ≤ 200$ |
| $5$ | $34$ | $1 ≤ N, S ≤ 500 000, 1 ≤ M ≤ 1 000 000$ |
 

h2. Exemplu