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