Королівство
King Kong — це грізний, але справедливий правитель Трансільванії. Його королівство складається з двох міст і N < 150 містечок, з'єднаних дорогами, які не перетинаються. Дороги двосторонні, і час на їх подолання однаковий в обох напрямках. У Конга є G < 353535 солдатів.
Через зростання контрабанди козячого сиру між двома містами, Конг повинен розмістити своїх солдатів на деяких дорогах так, щоб не можна було дістатися з одного міста до іншого, не зустрівши солдата. Солдатів не можна розміщувати всередині містечка, але їх можна розмістити на дорозі, так близько, як Конг забажає, до будь-якого містечка. Будь-яка кількість солдатів може бути розміщена на одній дорозі. Однак, якщо будь-яке з двох міст буде атаковане іноземною армією, король повинен мати можливість швидко перемістити всіх своїх солдатів до атакованого міста. Допоможіть йому розмістити солдатів так, щоб час мобілізації був мінімальним.
Зверніть увагу, що солдатів не можна розміщувати в жодному з міст чи містечок. Міста мають поштові індекси 95050 та 104729, тоді як містечка мають поштові індекси від 0 до N-1. Між будь-якою парою міст чи містечок буде не більше однієї дороги.
Вхідні дані
Вхід містить декілька тестових випадків. Перша строка кожного тестового випадку — це N, G та E, де N та G визначені вище, а E < 5000 — це кількість доріг. Далі йдуть E рядків, кожен з яких містить три цілі числа: A та B, поштові індекси кінцевих точок, і φ, час, необхідний для подолання дороги, φ < 1000. Останній рядок вводу — це рядок, що містить одне число 0.
Вихідні дані
Для кожного тестового випадку у вводі виведіть найкращий можливий час мобілізації з однією десятковою. Якщо даної кількості солдатів недостатньо, щоб зупинити контрабанду козячого сиру, виведіть "Impossible".