Вам дан связный неориентированный взвешенный граф. Вам гарантируется, что в графе существует хотя бы один эйлеров цикл, то есть цикл проходящий по всем ребрам и возвращающийся в изначальную вершину. Вам требуется найти минимальный вес всех ребер в каком-то из эйлеровых циклов, а среди всех циклов с минимальной суммой ребер выбрать тот, в котором стартовая вершина имеет наименьший номер. В ответе запишите через пробел номер стартовой вершины и стоимость цикла, то есть сумму весов всех ребер входящих в цикл.
Задача является в некотором роде задачей-шуткой, однако школьники тратят огромное время на то, чтобы фактически найти эйлеров цикл, хотя по условию гарантируется, что он есть. Заметим, что если есть хотя бы один эйлеров цикл, то он фактически единственный. Тогда сумма весов всех ребер и есть ответ, а минимальная вершина для старта — вершина с наименьшим номером. Задача может получить небольшое развитие. Достаточно спрашивать не про эйлеров цикл, а про эйлеров путь. Тогда возможных стартовых вершины ровно 2 — вершины с нечётной степенью. P.S. Полный граф на 5 вершинах, имеющий сакральный смысл для всего марафона Школково по Информатике является Эйлеровым.