eolymp
Змагання

NetOI-2011 Тур 3

Railway

Ліміт часу 3 секунди
Ліміт використання пам'яті 64 MiB

   В країні Олімпія трапилась економічна криза. Не оминуло це і місцеву залізницю. Після останніх реформ залізниця Олімпії стала складатись з N станцій та N-1 перегонів, які з'єднують ці станції. Кожна станція може бути безпосередньо з'єднана не більше, ніж з шістьма іншими станціями. Між будь-якою парою різних станцій існує лише один спосіб дістатися від першої станції до другої.

   Найбільших проблем залізниця Олімпії зазнає від розкрадачів, які вночі знімають рейки з залізничних колій. Злодії можуть починати свій рух з будь-якої станції та безперешкодно прямувати до будь-якої іншої станції. При цьому не можна проїжджати одну станцію більше, ніж один раз.

   Дирекція залізниці просить вас визначити найбільш можливий збиток та кількість способів його спричинити.

Вхідні дані

   Програма повинна прочитати ціле число N (1N100000) - кількість залізничних станцій, а потім N-1 трійок цілих чисел. Кожна трійка містить інформацію про один перегін. Перші два числа - номери станцій, які з'єднує даний перегін, третє число - довжина перегону в кілометрах (довжина не може перевищувати 1000 км).

Вихідні дані

   Програма повинна виводити два числа через пропуск - найбільший можливий збиток (сумарна довжина колій, які розкрадачі можуть розібрати) та кількість способів його спричинити.

Приклад

Вхідні дані #1
3 1 2 1 2 3 2
Вихідні дані #1
3 2