Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

Школы

(Время: 1 сек. Память: 16 Мб Сложность: 65%)

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

Считается, что школа имеет надежное электроснабжение, если она напрямую связана с источником «Майбуття», либо с одной из тех школ, которые имеют надежное электроснабжение.

Известна стоимость соединения между некоторыми парами школ. Мэр города решил выбрать одну из двух наиболее экономичных схем электроснабжения (стоимость схемы равняется сумме стоимостей соединений пар школ).

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

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

В первой строке входного файла INPUT.TXT два натуральных числа N и M – количество школ в городе и количество возможных соединений между ними соответственно (3 ≤ N ≤ 100, N ≤ M ≤ N∙(N-1)/2).

В каждой из последующих M строк находятся по три целых числа: Ai, Bi, Ci, где Ci – стоимость прокладки линии электроснабжения от школы Ai до школы Bi (1 ≤ Ci ≤ 300; i=1, 2, … , N).

Гарантируется, что существует хотя бы две различные схемы электроснабжения.

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

В выходной файл OUTPUT.TXT выведите два натуральных числа S1 и S2 – две наименьшие стоимости различных схем электроснабжения (S1 ≤ S2).

Пример

INPUT.TXTOUTPUT.TXT
15 8
1 3 75
3 4 51
2 4 19
3 2 95
2 5 42
5 4 31
1 2 9
3 5 66
110 121

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 Тренировочные олимпиады
 Введение
 Целочисленная арифметика
 Алгоритмы сортировки
 Длинная арифметика
 C++ Standard Template Library
 Динамическое программирование
 Комбинаторика
 Вычислительная геометрия
 Строки
 Структуры данных
 Теория графов - 1
 Теория графов - 2
 Алгоритм Флойда
 Алгоритм Форда-Беллмана
 Алгоритм Дейкстры
 Минимальный каркас
 Эйлеров цикл, конденсация
 Паросочетания
 A. Получи дерево
 B. Минимальный каркас
 C. Связанное множество
 D. Остовное дерево
 E. Школы
 F. Печатная схема

Красноярский краевой Дворец пионеров, (c)2006 - 2019, E-mail: admin@acmp.ru