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

bq. Ești Ghober-prost să mor eu

bq. Esti Ghober-prost sa mor eu

Friedrich Nietzsche

h2. Restricţii

Fie $S$ = suma tuturor $K$-urilor de la intrare.

* 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, 1 ≤ S, M ≤ 200 000, Graful este un lant$|
| $4$ | $26$ | $1 ≤ N ≤ 100 000, 1 ≤ S, M ≤ 200 000$ |
| $5$ | $24$ | $1 ≤ N ≤ 500 000, 1 ≤ S, M ≤ 1 000 000$ |
 

| $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