Зафод Билброкс — президент имперского галактического правительства. И совершенно случайно владеет предприятием, торгующим подержанными шариковыми ручками. Это сложный, высокодоходный и высоко конкурентный бизнес. Чтобы остаться лидером, приходится постоянно минимизировать издержки, чему замечательно помогает пост президента. Только нужно сохранять этот бизнес в тайне. Как президент, Зафод имеет доступ к чрезвычайно секретным и важным данным — точным затратам энергии на гиперпространственные переходы между планетами. Конечно, эта информация чрезвычайно полезна для его компании. Зафоду необходимо выбрать между планетами наименьшее возможное число переходов, так, чтобы с любой планеты на любую можно было попасть по выбранным переходам и суммарная стоимость переходов была минимальна. Задача несложная, если бы не надо было сохранять в тайне, что Зафод помогает своей компании секретной информацией. Поэтому Зафод решил найти не минимальный по стоимости вариант, а сразу следующий. Как рачительный хозяин, он хочет оценить всё же потерю в деньгах вследствие конспирации.

В первой строке записаны целые числа n и m — число планет в галактике и число гиперпереходов между ними (2 ≤ n ≤ 500; 1 ≤ m ≤ n (n − 1) / 2). Следующие m строк описывают эти гиперпереходы. i-я из них содержит целые числа a_i, b_i, w_i, означающие, что между планетами a_i и b_i в обе стороны есть переход стоимостью w_i единиц энергии (1 ≤ a_i, b_i ≤ n; 0 ≤ w_i ≤ 1000). Существует не более одного перехода между любыми двумя планетами. С любой планеты галактики можно попасть на любую другую посредством переходов.

Выдайте минимальный и следующий по затратам энергии набор переходов. Если существует несколько вариантов наборов переходов, выведите любой. Если какого-то из переходов не существует, обозначьте это стоимостью −1.