Время
Столкновение галактик неизбежно!
Галактика, управляемая загадочным MdI, пытается аннексировать наш Млечный Путь, но галактическое правительство намерено изменить ситуацию.
Наше разведывательное агентство проникло в штаб-квартиру врага и получило удивительную информацию. Враг перемещает свои подразделения по фиксированной схеме: для каждого форта часть подразделений перемещается в другие форты в каждом единичном отрезке времени (время полета незначительно).
Теперь правительство назначило время для атаки. Ваш приказ — вычислить слабые места. Однако, поскольку галактика врага находится очень далеко, требуется один единичный отрезок времени, чтобы долететь туда. Более того, мы уверены, что MdI распознает нашу цель и немедленно запустит все корабли, которые могут достичь нашей атакующей точки (через одну связь, независимо от её направления). Шпион сообщил вам, что эти силы являются только статистическими значениями, то есть своего рода индикатором в виде числа с плавающей запятой.
Входные данные
Первая строка ввода содержит количество тестов (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 – Сила войск, с которыми предстоит столкнуться в каждом форте. Обратите внимание, что связи используются в обоих направлениях.