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