Задача Minodd
Господин Дывак решил поехать к своей сестре. Планируя поездку, он узнал о стоимости проезда на всех автобусных рейсах их района. Но господин таки был чудак, потому что решил, что стоимость проезда к сестре должна составлять нечетное число копеек. С другой стороны, он хочет добраться дешевле всего, то есть найти самый дешевый среди тех маршрутов, в которых суммарная стоимость поездки является нечетной. Пересадки Дывака не пугают. Отдельные части маршрута могут стоить четное число копеек; нечетной должна быть суммарная стоимость всех использованных маршрутов.Рейсы выполняются между N населенными пунктами, среди которых село господина Дывака обозначено как №1, сестры — как №2. Для каждой пары пунктов или вообще не существует прямого сообщения, или стоимость проезда известна и одинакова в обоих направлениях. Из любого пункта гарантированно можно добраться до любого, но не исключено, что все возможные способы будут стоить четное число копеек.
Технические условия
Программа Minodd в первой строке читает с клавиатуры числа N и M — количество населенных пунктов и количество рейсов. Дальше считывает M строк по три натуральных числа i, j и cij — номера пунктов, которые соединяет рейс, и стоимость проезда. Среди этих M строк ни разу не повторяется одна и та же пара пунктов (в т.ч., когда те же два пункта переставлены местами). Никакой рейс не соединяет пункт сам с собой. 4≤N,M ≤ 500, 1≤c≤1000. Программа выводит на экран два числа через пробел - минимальную возможную суммарную стоимость проезда среди всех «нечетных» и минимальную возможную стоимость проезда среди всех возможных («четных», или «нечетных») маршрутов. Если не существует ни одного способа добраться за нечетную стоимость, первое число -1.
Пример
Ввод
4 5
1 2 202
1 3 202
1 4 202
2 4 202
3 4 101
Вывод 505 202