eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Надежные сети

Надежные сети

Лимит времени 1 секунда
Лимит использования памяти 122 MiB

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

Входные данные

Состоит из нескольких тестов. Каждый тест начинается со строки, содержащей пару целых чисел n (n15) и m (m20) - количество зданий (пронумерованных от 1 до n) и количество возможных соединений между зданиями. Каждая из следующих m строк имеет вид b[1] b[2]c (все числа натуральные), указывающая на то, что стоимость соединения зданий b[1] и b[2] равна с. Все связи двунаправленные.

Последний тест содержит n = m = 0 и не обрабатывается.

Выходные данные

Для каждого теста вывести одну строку, содержащую стоимость минимальной надежной сети. Если такая сеть существует, то вывод должен иметь формат:

The minimal cost for test case p is c.

где p номер теста (начиная с 1), а c стоимость. Если надежной сети не существует, следует вывести следующую строку:

There is no reliable net possible for test case p.

prb2622 - Copy.gif

Пример

Входные данные #1
4 5
1 2 1
1 3 2
2 4 2
3 4 1
2 3 1
2 1
1 2 5
0 0
Выходные данные #1
The minimal cost for test case 1 is 6.
There is no reliable net possible for test case 2.