Часування#6039
Зіткнення галактик наближається!
Галактика, якою керує таємничий MdI, намагається анексувати наш Чумацький Шлях, але галактичний уряд має плани змінити ситуацію.
Наше розвідувальне агентство проникло в штаб ворога і отримало несподівану інформацію. Ворог переміщує свої підрозділи за фіксованою схемою: для кожного форту частина підрозділів переміщується до інших фортів у кожну одиницю часу (час польоту незначний).
Тепер уряд визначив час для атаки. Ваше завдання — обчислити слабкі місця. Але оскільки галактика ворога знаходиться дуже далеко, потрібно одна одиниця часу, щоб туди долетіти. Крім того, ми також впевнені, що MdI розпізнає нашу ціль і негайно запустить всі кораблі, які можуть досягти нашої точки атаки (через один зв'язок, незалежно від його напрямку). Шпигун повідомив, що ці сили є лише статистичними значеннями, тобто якимось індикатором у вигляді числа з плаваючою комою.
Перша строка вхідних даних містить кількість тестових випадків (1 \leq T \leq 10). Кожен тестовий випадок починається з одного рядка, що містить три цілі числа, які вказують кількість ворожих фортів (1 \leq N \leq 100), кількість зв'язків (0 \leq l \leq (N-1)^2) та час від тепер, коли атакувати (0 \leq t \leq 5000). Другий рядок містить дійсних чисел u_i (0 \leq u_i \leq 1000), що вказують на силу розміщених військ у кожному форті, за якими слідують рядків, що містять зв'язки. Кожен зв'язок описується двома цілими числами s_j (0 \leq s_j < N), t_j (0 \leq t_j < N), що описують джерело та ціль зв'язку, і одним дійсним числом p_j (0 < p_j \leq 1), часткою підрозділів, що передаються з s_j до t_j у кожну одиницю часу.
Виведіть найнижчий індикатор ворожої галактики з абсолютною або відносною похибкою менше 10^{-6}.
Рисунок 1 — Статистичні сили першого зразка до і після першого кроку часу.
Рисунок 2 — Сила військ, з якими потрібно зіткнутися в кожному форті. Зверніть увагу, що зв'язки використовуються в обох напрямках.
Приклад 1