Задача Railway
В країні Олімпія трапилась економічна криза. Не оминуло це і місцеву залізницю. Після останніх реформ залізниця Олімпії стала складатись з N станцій та N-1 перегонів, які з'єднують ці станції. Кожна станція може бути безпосередньо з'єднана не більше, ніж з шістьма іншими станціями. Між будь-якою парою різних станцій існує лише один спосіб дістатися від першої станції до другої.
Найбільших проблем залізниця Олімпії зазнає від розкрадачів, які вночі знімають рейки з залізничних колій. Злодії можуть починати свій рух з будь-якої станції та безперешкодно прямувати до будь-якої іншої станції, рухаючись лише по колії, а потяги в Олімії ночами не ходять - шлях вільний. Але злодіїї не можуть проїжджати одну станцію більше, ніж один раз - бояться.
Дирекція залізниці просить вас визначити найбільший збиток та кількість способів його спричинити.
Технічні умови: Програма повинна прочитати з клавіатури натуральне число N (1 <= N <= 100000) -- кількість залізничних станцій, а потім N-1 трійок натуральних чисел. Кожна трійка містить інформацію про один перегін. Перші два числа - номери станцій, які з'єднує даний перегін, третє число - довжина перегону в кілометрах (довжина не може перевищувати 1000 км).
Програма повинна виводити на екран два числа через пробіл - найбільш можливий збиток (сумарна довжина колій, які розкрадачі можуть розібрати) та кількість способів його спричинити.
Приклади:
Введення: 3 1 2 1 2 3 2
Виведення: 3 2
Введення: 5 1 2 1 1 3 1 1 4 1 1 5 1
Виведення: 2 12