Dəmir yolu#2775
Olimpiya ölkəsində iqtisadi böhran baş verdi və bu, yerli dəmir yolunu da təsirləndirdi. Son islahatlardan sonra Olimpiya dəmir yolu stansiyadan və bu stansiyaları birləşdirən N-1 keçiddən ibarətdir. Hər bir stansiya birbaşa altıdan çox olmayan digər stansiyalarla birləşdirilə bilər. İstənilən iki fərqli stansiya arasında birinci stansiyadan ikinciyə çatmağın yalnız bir unikal yolu var.
Olimpiya dəmir yolunun əsas problemi gecələr relsləri çıxaran oğrulardır. Oğrular istənilən stansiyadan hərəkət edib, istənilən digər stansiyaya gedə bilər, lakin bir stansiyadan bir dəfədən artıq keçmək olmaz.
Dəmir yolu rəhbərliyi sizdən ən böyük mümkün ziyanı (oğruların sökə biləcəyi relslərin ümumi uzunluğunu) və bunu törətməyin yollarının sayını müəyyən etməyi istəyir.
Proqram tam ədədini (1 \leq N \leq 100{,}000) — dəmir yolu stansiyalarının sayını, sonra isə N-1 üçlü tam ədəd oxumalıdır. Hər üçlük bir keçid haqqında məlumatı ehtiva edir: ilk iki ədəd keçidin birləşdirdiyi stansiyaların nömrələridir, üçüncü ədəd isə keçidin uzunluğunu kilometr ilə göstərir (uzunluq km-dən çox ola bilməz).
Proqram boşluqla ayrılmış iki ədəd çıxarmalıdır: ən böyük mümkün ziyan (oğruların sökə biləcəyi relslərin ümumi uzunluğu) və bunu törətməyin yollarının sayı.
Nümunə 1