F. Yig‘ilish xonasi

Litsey binosida N ta xona bor, ular 1 dan N gacha raqamlangan. Xonalar N − 1 ta yo‘lak bilan shunday ulanganki, istalgan xonadan istalgan xonaga aynan bitta yo‘l bilan borish mumkin. j-yo‘lak uⱼ va vⱼ xonalarni ulaydi, uzunligi wⱼ metr.

Hozir i-xonada aᵢ ta o‘quvchi bor. Direktor bitta xonani tanlab, hammani shu yerga yig‘ilishga chaqirmoqchi. Har bir o‘quvchi tanlangan xonaga yagona yo‘l bo‘ylab yuradi.

Barcha o‘quvchilar bosib o‘tadigan umumiy masofa eng kam bo‘lishi uchun qaysi xonani tanlash kerak? Bir nechta xona mos kelsa, raqami eng kichigini tanlang.

Kirish ma’lumotlari

Birinchi qatorda bitta butun son N — xonalar soni.

Ikkinchi qatorda N ta butun son a₁, a₂, …, aₙ — xonalardagi o‘quvchilar soni.

Keyingi N − 1 qatorning har birida uchta butun son uⱼ, vⱼ, wⱼ — yo‘lak.

Chiqish ma’lumotlari

Bitta qatorda ikkita butun son — eng kam umumiy masofa (metr) va tanlangan xona raqami.

Cheklovlar

• 1 ≤ N ≤ 2·10⁵
• 0 ≤ aᵢ ≤ 1000
• 1 ≤ uⱼ, vⱼ ≤ N, uⱼ ≠ vⱼ, 1 ≤ wⱼ ≤ 1000
• Yo‘laklar daraxt hosil qiladi
• Javob 32 bitli songa sig‘masligi mumkin: C++ da long long ishlating.

1-misol: yig‘ilish 2-xonada bo‘lsa, 1-xonadagi o‘quvchi 3 m, 4-xonadagi 2 kishi 1 m dan, 5-xonadagi 3 kishi 6 m dan yuradi: 3 + 2 + 18 = 23. 4-xonada ham 23 chiqadi (4 + 4 + 15), boshqa xonalarda ko‘proq. Eng kichik raqam — 2.

2-misol: xona bitta — hech kim yurmaydi.