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 <tex>a_1, a_2, \dots, a_K</tex> (pentru <tex>K \ge 1</tex>), unde există o muchie între <tex>a_i</tex> şi <tex>a_{i+1}</tex> pentru orice <tex>1 \le i < K</tex>.

Un lanţ se defineşte ca fiind o înşiruire de noduri distincte <tex>a_1, a_2, \dots, a_K</tex> (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