Zaphod Beeblebrox oslavuje svoje 47. narodeniny... opäť. Pozval si na večierok $K$ zo svojich priateľov.
V galaxii je $N$ planét, na ktorých sa bude večierok konať. Žiaden zo Zaphodových priateľov nebýva na rovnakej planéte a nikto z nich nebýva na planéte, kde sa koná večierok.
Niektoré dvojice planét sú prepojené obojsmernými intragalaktickými diaľnicami. Pri každej diaľnici poznáme jej koncové body a jej dĺžku v svetelných rokoch.
Každý Zaphodov priateľ má vlastnú osobnú kozmickú loď. Každá kozmická loď má pevne danú rýchlosť v svetelných rokoch za sekundu.
Okrem diaľnic existuje ešte jedna možnosť cestovania: teleporty. Existuje niekoľko spoločností, ktoré poskytujú služby teleportácie. Každá spoločnosť obsluhuje množinu planét a množiny planét obsluhované rôznymi spoločnosťami sú navzájom disjunktné.
Počas akejkoľvek časti cesty môžu Zaphodovi priateľi používať teleporty na okamžité presunutie svojich kozmických lodí medzi ľubovoľnými dvoma planétami, ktoré obsluhuje tá istá spoločnosť.
Môžete predpokladať, že navigačné systémy kozmických lodí vyberajú najrýchlejšie trasy, aby sa dostali na večierok. Pre každého Zaphodovho priateľa vypočítajte čas, za ktorý sa k večierku dostane, a vypíšte súčet týchto časov.
Prvý riadok vstupu obsahuje tri celé čísla: $N$, $M$ a $K$ $(1 \leq N \leq 50 000, 1 \leq M \leq 200 000, 1 \leq K < N)$. Tu $N$ je počet planét v univerze, $M$ je počet diaľnic a $K$ je počet Zaphodových priateľov. Planéty sú očíslované od 1 po $N$ tak, aby priateľi bývali na planétach 1 až $K$ a večierok sa konal na planéte $N$.
Ďalší riadok obsahuje reťazec so presne $N$ znakmi. $i$-ty znak v tomto reťazci určuje spoločnosť teleportačnej služby, ktorá obsluhuje $i$-tu planétu. Každá spoločnosť je identifikovaná nejakým malým písmenom. Planéta, ktorá nie je obsluhovaná žiadnou spoločnosťou, je označená znakom #.
Nasledujúcich $M$ riadkov obsahuje po tri celé čísla $x$, $y$, $d$ $(1 \leq x,y \leq N, 1 \leq d \leq 2^{30})$, ktoré opisujú jednu diaľnicu: planéty $x$ a $y$ sú spojené diaľnicou dĺžky $d$.
Nasleduje $K$ riadkov, pričom $i$-ty z nich obsahuje jedno celé číslo $s_i$ $(1 \leq s_i \leq 100)$ — rýchlosť kozmickej lode priateľa, ktorý žije na planéte $i$.
Môžete predpokladať, že je vždy možné cestovať medzi ľubovoľnými dvoma planétami (pomocou vhodnej kombinácie diaľnic a teleportov).
Vypíšte jeden riadok s jedným reálnym číslom — celkový čas cesty Zaphodových priateľov.
Váš odpoveď sa bude považovať za správnu, ak má absolútnu alebo relatívnu chybu najviac $10^{-7}$.
4 3 2
#aa#
1 3 7
2 4 2
3 4 5
4
3
2.91666666667
Prvý priateľ ide diaľnicou z planéty #1 na #3, teleportuje na #2 a potom ide diaľnicou na #4, čo bude trvať $9 / 4 = 2.25$ sekúnd. Druhý priateľ ide iba diaľnicou z planéty #2 na #4, čo bude trvať $2 / 3 = 0.66666667$ sekúnd. Celkový čas cesty je $2.25 + 0.66666667 = 2.91666667$.