Mazākais reizinājums

Pētnieks Konrāds šobrīd analizē kādas transporta firmas materiālu pārvadāšanas maršrutus starp $N$ pilsētām. Viņš ir noskaidrojis, ka katrs pārvadājums starp kādām divām pilsētām notiek pa maršrutu, kas sadalīts vienā vai vairākos posmos tā, ka katrs posms saista tieši divas pilsētas. Turklāt maršruts starp jebkurām divām pilsētām ir viens vienīgs - vienmēr viena un tā pati posmu virkne.

Vienas šādas sistēmas ar pilsētas savienojošajiem posmiem piemērs parādīts attēlā.

Konrāds ir noskaidrojis, ka pārvadājumu izmaksas katrā posmā var izteikt kā veselu nenegatīvu skaitli, kas dažādiem posmiem var atšķirties. Viņš vēlas noteikt, kuriem pilsētu pāriem to savienojošā maršruta posmu izmaksu reizinājums ir vismazākais.

Attēlā dotajam piemēram ir $10$ pilsētu pāri ar to savienojošo maršrutu posmu izmaksu reizinājumu $1$: $1-2$, $1-4$, $2-4$, $3-5$, $3-6$, $3-7$, $5-6$, $5-7$, $6-7$, $8-9$.

Uzrakstiet datorprogrammu, kas dotam pilsētu sistēmas aprakstam nosaka mazāko kādu pilsētu pāri savienojošā maršruta posmu izmaksu reizinājumu $R_{\min}$ un pilsētu pāru, kuru savienojošā maršruta posmu izmaksu reizinājums ir $R_{\min}$, skaitu $S$!

Pirmajā rindā dots naturāls skaitlis - pilsētu skaits $N$ ($2 \leq N \leq 10^5$). Pilsētas sanumurētas ar naturāliem skaitļiem no $1$ līdz $N$ pēc kārtas.

Nākamajās $N-1$ rindās katrā dots viena posma apraksts - pilsētu numuru pāris $a$ un $b$ ($1 \leq a, b \leq N, a \neq b$) un posma starp šīm pilsētām izmaksu vērtība $c_{a, b}$ ($0 \leq c_{a, b} \leq 10^9$).

Starp katriem diviem blakus skaitļiem ir tukšumzīme.

Vienīgajā rindā jāizvada divi veseli nenegatīvi skaitļi - mazākais kādu pilsētu pāri savienojošā maršruta posmu izmaksu reizinājums $R_{\min}$ un pilsētu pāru, kuru savienojošā maršruta posmu izmaksu reizinājums ir $R_{\min}$, skaits $S$.

Starp skaitļiem jābūt tukšumzīmei.