Petrică are la dispoziţie următoarea operaţie, pe care o poate face *o singură dată*: alege un lanţ al arborelui şi înjumătăţeşte costul tuturor muchiilor de pe acel lanţ. Ajutaţi-l să găsească cea mai mică valoare a unui arbore obţinut după aplicarea operaţiei.

Un lanţ se defineşte ca fiind o înşiruire de noduri distincte $a_1, a_2, \dots, a_K$ (pentru $K \ge 1$), unde există o muchie între $a_i$ şi $a_{i+1}$ pentru orice $1 \le i < K$.

Un lanţ se defineşte ca fiind o înşiruire de noduri distincte a_1, a_2, \dots, a_K (pentru $K \ge 1$), unde există o muchie între $a_i$ şi $a_{i+1}$ pentru orice $1 \le i < K$.

h2. Date de intrare