Задача Q. Распространение примеси ≡

Условие

Жители одного крупного города озаботились сложившейся в его окрестностях экологической обстановкой. Дело в том, что в прилегающих к нему районах имеется достаточно большое число промышленных предприятий, вредные выбросы которых неблагоприятным образом влияют на окружающую среду. Ситуация усугубляется еще и тем, что расположены они в основном по берегам рек, воды которых также идут на хозяйственные нужды горожан.

Для того, чтобы оценить величину наносимого ущерба, понадобилось провести ряд исследований, направленных на выявление наиболее вредных объектов промышленности. Однако представители крупных коммерческих предприятий отказались предоставлять точную информацию об объемах сбрасываемых в реку загрязнений. В связи с этим, члены экологического общества поставили перед собой задачу — попытаться восстановить их значения, руководствуясь только лишь данными, полученными из открытых источников.

Карта речной системы представляет собой ориентированный бесконтурный граф (сеть), в узлах которого располагаются очистные сооружения и разнообразные источники загрязнений. На входе указанной сети располагаются узлы, связанные с крупнейшими заводами. Каждый i-й завод непрерывно за одну единицу времени сбрасывает в реку ровно X_i тонн химических отходов.

Известно, что при прохождении через k-й промежуточный узел концентрация примеси изменяется на аддитивную константу F_k. Процент примеси, пропускаемый через ребро, направленное из узла с номером k в узел с номером l, определяется коэффициентом W_{k l}.

На выходе располагаются системы сбора воды с установленными на них датчиками, которые регистрируют количество примеси Y_j, проходящее через них за одну единицу времени.

По имеющимся данным требуется определить концентрацию примеси, выбрасываемую каждым отдельным заводом.

Формат входного файла

Во входном файле "input.txt" хранится карта речной сети, записанная в следующем виде.

Вначале идет пара натуральных значений n и m — число вершин и ребер в таком графе. За ними следует набор из m ребер, каждое из которых задается тремя значениями: k и l — номера вершин, которые оно соединяет; W_{k l} — весовой коэффициент.
При этом полагается, что нумерация вершин начинается с нуля.

На входе такой сети располагаются вершины, связанные с основными заводами. В отличие от остальных вершин, они не имеют входящих ребер. Вершины, имеющие как входные так и выходные ребра, связаны с промежуточными узлами, а вершины, не имеющие выходных ребер — с конечными.

Далее следует список, в котором каждому промежуточному узлу с номером k ставится в соответствие вещественная константа F_k, а каждому конечному узлу с номером j — значение Y_j.

Порядок следования узлов в таком списке не гарантирован!

Формат выходного файла

Если задача имеет единственное решение, в выходной файл "output.txt" выводится строка 'SOLUTION:',
за которой следует список из номеров входных узлов i и соответствующих им значений X_i,
указанных с точностью до 5-го знака после запятой.

В противном случае, выходной файл должен содержать строку 'INFINITY!'.

Ограничения

Гарантируется, что точное решение всегда существует
и удовлетворяет следующим соотношениям: 0 ≤ X_i ≤ 10.

Все тесты подобраны таким образом, чтобы снизить влияние погрешности
машинного округления на результат решения.

Гарантируется отсутствие висячих вершин
(не связанных ни с одним из ребер).

Число ребер, исходящих из одной вершины, не превосходит 10,
а их суммарный вес равен 1.

0 ≤ F_k ≤ 10, 2 ≤ n ≤ 1000, 0 < m.

Примеры тестов

10 9
0 3 1.00000
1 6 0.75000
1 4 0.25000
4 6 1.00000
6 3 0.50000
6 7 0.50000
2 5 1.00000
5 8 0.50000
5 9 0.50000

4 2.50480
5 1.39000
6 0.75630

3 5.30580
7 3.41550
8 1.91030
9 1.91030

SOLUTION:
0 1.89030
1 3.56990
2 2.43060

8 7
0 3 0.75000
0 4 0.25000
3 5 0.50000
3 6 0.50000
4 7 1.00000
1 4 1.00000
2 4 1.00000

3 1.36070
4 2.04590

5 2.71740
6 2.71740
7 7.41445

INFINITY!