Kauniilla kampuksella Panda ja hänen ystävänsä ovat tapaamassa aterian merkeissä. He nauttivat yhteisestä ajasta matkan varrella, sillä silloin he voivat jutella vapaasti keskenään.

Kampus mallinnetaan yhtenäisenä suuntaamattomana verkkona, jossa on $n$ solmua ja $m$ pituuksilla varustettua kaarta. Tapaamispaikka on ostoskeskus, joka sijaitsee solmussa $1$. $k$ ystävää lähtee liikkeelle eri solmuista ja kulkee kohti ostoskeskusta. Kaikki ystävät liikkuvat samalla nopeudella ($1$ pituusyksikkö aikayksikköä kohti), ja he saavat vaihtaa kulkusuuntaa missä tahansa kohdassa kaarella (katso esimerkin selitys).

Olkoon $t_{\text{meet}}$ varhaisin mahdollinen ajanhetki, johon mennessä kaikki ystävät voivat saavuttaa ostoskeskuksen. Tämän varhaisimman mahdollisen tapaamisajan perusteella etsi jokaiselle ystävälle erikseen suurin mahdollinen kokonaisaika, jonka hän voi viettää seurassa (mikä tarkoittaa, että vähintään yksi muu ystävä on täsmälleen samassa paikassa verkossa, joko solmussa tai jossakin kohdassa kaarella) ennen lopullista kokoontumista ostoskeskuksessa.

Kun tarkastellaan tiettyä ystävää $i$, kaikkien muiden ystävien $j \neq i$ reitit ja liikkumisstrategiat optimoidaan maksimoimaan ystävän $i$ seurassa viettämä aika, kunhan kaikki ystävät saapuvat ostoskeskukseen viimeistään ajanhetkellä $t_{\text{meet}}$.

Syöte

Ensimmäinen rivi sisältää kokonaisluvun $T$ ($1 \le T \le 10^4$), joka ilmaisee testitapausten lukumäärän.

Jokaisessa testitapauksessa ensimmäinen rivi sisältää kolme kokonaislukua $n, m, k$ ($2 \le n \le 3 \times 10^5$, $n - 1 \le m \le 10^6$, $2 \le k \le n$), jotka ilmaisevat solmujen, kaarien ja ystävien lukumäärät tässä järjestyksessä.

Toinen rivi sisältää $k$ eri kokonaislukua $a_1, a_2, \ldots, a_k$ ($1 \le a_i \le n$), jotka ilmaisevat ystävien lähtösolmut.

Seuraavat $m$ riviä sisältävät kukin kolme kokonaislukua $u, v, w$ ($1 \le u, v \le n$, $u \neq v$, $1 \le w \le 10^9$), jotka ilmaisevat solmujen $u$ ja $v$ välisen kaaren, jonka pituus on $w$. Verkko on yhtenäinen, eikä siinä ole moninkertaisia kaaria tai silmukoita.

Lukujen $n$ summa yli kaikkien testitapausten ei ylitä arvoa $3 \times 10^5$, eikä lukujen $m$ summa yli kaikkien testitapausten ylitä arvoa $10^6$.

Tuloste

Tulosta jokaista testitapausta kohden rivi, joka sisältää $k$ välilyönnein erotettua liukulukua, joista jokainen on muotoiltu täsmälleen yhden desimaalin tarkkuudella, kuvaten kunkin ystävän suurinta mahdollista seurassa vietettyä aikaa.

Esimerkit

Syöte 1

3
4 3 2
3 4
1 2 3
3 2 1
4 2 1
2 1 2
1 2
1 2 3
3 2 3
1 2 3
1 2 3
1 3 5

Tuloste 1

3.0 3.0
1.5 1.5
3.5 3.5 2.5

Huomautus

Esimerkin kolmannessa testitapauksessa varhaisin tapaamisaika ostoskeskuksessa on $5$ aikayksikköä.

• Solmuista $1$ ja $2$ lähtevät ystävät voivat kohdata kaaren $(1, 2)$ puolivälissä $1.5$ aikayksikössä, kulkea yhdessä takaisin ostoskeskukseen toisessa $1.5$ yksikössä ja odottaa sitten $2$ yksikköä ostoskeskuksessa, mikä tekee yhteensä $3.5$ yksikköä yhdessäoloa.
• Solmusta $3$ lähtevä ystävä kohtaa solmusta $1$ lähtevät ystävät kaaren $(1, 3)$ puolivälissä $2.5$ yksikössä ja palaa heidän kanssaan $2.5$ yksikössä, mikä tekee yhteensä $2.5$ yksikköä yhdessäoloa.