$n$ ta qishloqni yo‘l bilan bog‘lash kerak: istalgan qishloqdan istalganiga (boshqa qishloqlar orqali bo‘lsa ham) borish mumkin bo‘lsin. $m$ ta mumkin bo‘lgan yo‘l va har birini qurish narxi ma’lum. Eng kam umumiy narxni toping.
Kirish ma‘lumotlari
Birinchi qatorda $n$ va $m$ ($1 \le n \le 10^5$, $0 \le m \le 10^5$). Keyingi $m$ ta qatorda $u$, $v$, $w$ — $u$ va $v$ qishloqlar orasidagi yo‘l narxi ($1 \le w \le 10^6$).
Chiqish ma‘lumotlari
Eng kam umumiy narx; hamma qishloqni bog‘lab bo‘lmasa, -1.
Misollar
Kirish
4 5 1 2 3 2 3 1 1 3 2 3 4 4 1 4 10
Chiqish
7
Kirish
3 1 1 2 5
Chiqish
-1