D. Гоёмсог зам

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Олон жилийн өмнө Азийн нэгэн оронд иргэний дайн болсон юм. Энэ улсын $n$ хот бүгд дайнд оролцжээ. Дайны үед нэг хот нь арми бүрдүүлж нөгөө нэг хотын эсрэг илгээдэг байв.

Тус улсад замын технологи төдийлөн сайн хөгжөөгүй учраас хотуудыг холбосон нийтдээ яг $n-1$ тооны зам байдаг. Энэ замуудаар аль ч хотоос өөр нэг хот руу хүрэх боломжтой байв.

Дайны үеэр Дорнын ард түмэн байгалийн гоо үзэсгэлэнг биширдэг, оюун санааны хувьд баялаг хэвээр байжээ. Мөн ирэх зуунд энэ агуу довтолгооны талаарх дурсамжийг хадгалж үлдэхийн тулд тэд армийнхны ихэнх цагаа өнгөрүүлдэг тэрхүү замаар нэг нэг мод тарьжээ.

Саяхан дайны баримтууд олдсон ба үүнээс хот бүр бусад хотууд руугаа яг нэг удаа довтолж байсан болох нь маш тодорхой харагдаж байв. Нийтдээ $n(n-1)$ довтолгоон болж өнгөрчээ. Бид бүгд энэ дайны дараа аль зам нь хамгийн гоёмсог болохыг, өөрөөр хэлбэл аль зам дээр тэд хамгийн олон мод тарьсан болохыг бодоцгоож байлаа.

Оролт

Эхний мөр нь хотуудын тоог харуулах $n$ ($2≤n≤10^{5}$) бүхэл тоог агуулна. Дараагийн $n-1$ мөрүүд тус бүр нь $3$ бүхэл тоог агуулна. Үүнд: $i$-р замаар холбогдсон хотуудын дугаар болох $a_{i}, b_{i}$ ($1≤a_{i}, b_{i}≤n$) болон уг замаар армийнхны явсан өдрүүдийн тоо болох $d_{i}$ ($1≤d_{i}≤10^{9}$) тоонууд. Хэд хэдэн замын урт давхцаж болно.

Гаралт

Эхний мөрөнд хамгийн гоёмсог зам дээрх моддын тоо болон хамгийн гоёмсог замуудын тоог харуулах $2$ бүхэл тоог хэвлээрэй. $2$ дахь мөрөнд хамгийн гоёмсог замуудыг дугаараар нь жагсаан хэвлээрэй. Замууд нь оролтонд өгөгдсөн дарааллаараа $1$-ээс $(n-1)$ хүртэл дугаарлагдана.

С++ хэлэнд $64$ битийн бүхэл тоог унших, бичихдээ %lld тодорхойлогчийг битгий ашиглаарай. Харин %I64d тодорхойлогчийг эсвэл cin, cout урсгалуудыг ашиглах нь дээр байдаг.

Орчуулсан: Солонго

Жишээ тэстүүд

Оролт
2
2 1 5
Гаралт
2 1
1 
Оролт
6
1 2 1
1 3 5
3 4 2
3 5 3
3 6 4
Гаралт
16 1
2 
Сэтгэгдлүүдийг ачааллаж байна...