NetOI-2011 Stage 3
Railway
В країні Олімпія трапилась економічна криза. Не оминуло це і місцеву залізницю. Після останніх реформ залізниця Олімпії стала складатись з N станцій та N-1 перегонів, які з'єднують ці станції. Кожна станція може бути безпосередньо з'єднана не більше, ніж з шістьма іншими станціями. Між будь-якою парою різних станцій існує лише один спосіб дістатися від першої станції до другої.
Найбільших проблем залізниця Олімпії зазнає від розкрадачів, які вночі знімають рейки з залізничних колій. Злодії можуть починати свій рух з будь-якої станції та безперешкодно прямувати до будь-якої іншої станції. При цьому не можна проїжджати одну станцію більше, ніж один раз.
Дирекція залізниці просить вас визначити найбільш можливий збиток та кількість способів його спричинити.
Input data
Програма повинна прочитати ціле число N (1 ≤ N ≤ 100000) - кількість залізничних станцій, а потім N-1 трійок цілих чисел. Кожна трійка містить інформацію про один перегін. Перші два числа - номери станцій, які з'єднує даний перегін, третє число - довжина перегону в кілометрах (довжина не може перевищувати 1000 км).
Output data
Програма повинна виводити два числа через пропуск - найбільший можливий збиток (сумарна довжина колій, які розкрадачі можуть розібрати) та кількість способів його спричинити.
Examples
3 1 2 1 2 3 2
3 2