ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

1266. Закон Кирхгоффа

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Папа у Васи силён, как известно, в математике. А сын, вместо того, чтобы идти по стопам отца, изучает в школе физику. Вот как-то обратился Вася к папе с просьбой помочь решить простую задачку — найти сопротивление системы резисторов. Папа и отвечает: да тут и думать нечего, нумеруешь все узлы, где проводники соединяются, пишешь закон I=U/R для каждого проводника. Ещё надо вспомнить что сумма токов на каждом узле, кроме начального и конечного — нулевая, потенциал в первом узле можешь считать единичным, в последнем — нулевым. Вот и получится простенькая система линейных уравнений. Из неё находятся все потенциалы в промежуточных узлах и токи между всеми узлами, делишь напряжение на суммарный ток из первого узла и…
Но Вася-то в математике не силён, пришлось папе самому написать систему и решить. А Вася заглядывает в конец задачника и говорит: там ответ другой! Попробовал папа решить снова, и правда — другой ответ. Ну а Вася, посмотрев в задачник, говорит: снова не то. Папа в третий раз аккуратно перерешивает задачу, а Вася опять за своё. Надоело папе вручную систему пересчитывать, решил он компьютер приспособить, благо студенты матмеха УрГУ готовы бесплатно написать нужную программу.

Исходные данные

В первой строке содержатся числа N и M, N — количество узлов электрической цепи (2 ≤ N ≤ 20), M — количество резисторов (1 ≤ M < 1000). Далее следуют M строк, содержащих три положительных целых числа Ai, Bi и Ri. Каждая такая строка описывает один резистор, имеющий сопротивление Ri и соединяющий узлы Ai и Bi (1 ≤ Ai < BiN; 1 ≤ Ri ≤ 1000). Между двумя узлами может находиться много резисторов.

Результат

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

Пример

исходные данныерезультат
4 5
1 2 15
2 4 5
1 3 10
3 4 10
2 3 1
9.40
Автор задачи: Александр Клепинин (подготовил — Станислав Васильев)
Источник задачи: Чемпионат Уральского государственного университета, 25 октября 2003 года