BS-O2. Yengil yo‘l

Viloyatda n ta shahar va m ta ikki tomonlama yo‘l bor; har yo‘lning og‘irligi (qiyinligi) cᵢ. Yuk mashinasi 1-shahardan n-shaharga borishi kerak va ko‘pi bilan K ta yo‘ldan o‘tishi mumkin (yoqilg‘isi shuncha yetadi). Yo‘lni shunday tanlangki, undagi eng og‘ir yo‘l imkon qadar yengil bo‘lsin. Shu og‘irlikni chiqaring. Yetib bo‘lmasa — -1. n = 1 bo‘lsa, javob 0.

Og‘irlik chegarasi W berilsa, faqat ≤ W yo‘llardan foydalanib eng kam nechta yo‘l bilan yetish mumkinligini BFS beradi.

Kirish ma’lumotlari

Birinchi qatorda n, m, K. Keyingi m qatorda yo‘l: u v c (bir shahardan o‘ziga yo‘l yoki takroriy yo‘llar bo‘lishi mumkin).

Chiqish ma’lumotlari

Bitta son — eng og‘ir yo‘lning eng kichik qiymati yoki -1.

Cheklovlar

1 ≤ n ≤ 2·10⁴; 1 ≤ m ≤ 5·10⁴; 1 ≤ K ≤ n; 1 ≤ cᵢ ≤ 10⁹.