~/algor $ cat masalalar/minimal-qamrovchi-daraxt
Graf-05
Minimal qamrovchi daraxt
Muallif:
Iqbolshoh Ilhomjonov
O'rtacha
1000 ms
128 MB
66%
$n$ ta cho'qqi va $m$ ta yo'naltirilmagan qirradan iborat graf berilgan; har bir qirraning og'irligi $w$ bor. Cho'qqilar $1$ dan $n$ gacha raqamlangan. Grafning minimal qamrovchi daraxti — barcha cho'qqilarni bog'lovchi va og'irliklari yig'indisi eng kichik bo'lgan qirralar to'plami. Shu yig'indini toping. Graf bog'liq bo'lmasa, $-1$ chiqaring.
Kiruvchi ma'lumotlar
Birinchi qatorda ikkita butun son: $n$ va $m$. Keyingi $m$ ta qatorning har birida uchta butun son: $u$, $v$ va $w$ — qirra tutashtirgan cho'qqilar va qirra og'irligi.
Chiquvchi ma'lumotlar
Bitta butun son — minimal qamrovchi daraxt og'irligi yoki $-1$.
Izoh
$1 \le n \le 10^{5}$
$0 \le m \le 2 * 10^{5}$
$1 \le u, v \le n$
$-10^{9} \le w \le 10^{9}$
Misollar
Kirish #1
4 5 1 2 1 1 3 4 2 3 2 2 4 5 3 4 3
Chiqish #1
6
Kirish #2
3 1 1 2 5
Chiqish #2
-1