Á fallegu háskólasvæði eru Panda og vinir hans að hittast til að borða saman. Þeir njóta þess að verja tíma saman á leiðinni því þá geta þeir spjallað frjálslega hver við annan.

Háskólasvæðið er sett fram sem samanhangandi, óstefnt net með $n$ hnútum og $m$ leggjum með lengdum. Fundarstaðurinn er verslunarmiðstöðin, sem er staðsett í hnúti $1$. $k$ vinir leggja af stað frá ólíkum hnútum og ferðast til verslunarmiðstöðvarinnar. Allir vinirnir hreyfast á sama hraða ($1$ lengdareiningu á tímaeiningu) og mega breyta um stefnu á hvaða stað sem er á legg (sjá skýringu á sýnidæmi).

Látum $t_{\text{meet}}$ vera fyrsta mögulega tímapunktinn þannig að allir vinirnir geti verið komnir í verslunarmiðstöðina á þeim tíma. Út frá þessum fyrsta mögulega fundartíma, finndu fyrir hvern vin í sitt hvoru lagi mesta heildartíma sem hann getur varið í félagsskap (þ.e. að minnsta kosti einn annar vinur er á nákvæmlega sama stað á netinu, sem gæti verið hnútur eða staðsetning á legg) áður en allir safnast saman í verslunarmiðstöðinni.

Þegar tiltekinn vinur $i$ er skoðaður eru leiðir og hreyfingaráætlanir allra hinna vinanna $j \neq i$ bestaðar til að hámarka tímann í félagsskap fyrir vin $i$, svo framarlega sem allir vinirnir koma í verslunarmiðstöðina eigi síðar en á tímanum $t_{\text{meet}}$.

Inntak

Fyrsta línan inniheldur heiltölu $T$ ($1 \le T \le 10^4$), sem táknar fjölda prófunartilvika.

Fyrir hvert prófunartilvik inniheldur fyrsta línan þrjár heiltölur $n, m, k$ ($2 \le n \le 3 \times 10^5$, $n - 1 \le m \le 10^6$, $2 \le k \le n$), sem tákna fjölda hnúta, leggja og vina, í þeirri röð.

Önnur línan inniheldur $k$ ólíkar heiltölur $a_1, a_2, \ldots, a_k$ ($1 \le a_i \le n$), sem tákna upphafshnúta vinanna.

Næstu $m$ línur innihalda hver um sig þrjár heiltölur $u, v, w$ ($1 \le u, v \le n$, $u \neq v$, $1 \le w \le 10^9$), sem gefa til kynna legg á milli hnúts $u$ og $v$ af lengd $w$. Netið er samanhangandi og hefur enga tvöfalda leggi eða sjálflykkjur.

Summa $n$ yfir öll prófunartilvik fer ekki yfir $3 \times 10^5$ og summa $m$ yfir öll prófunartilvik fer ekki yfir $10^6$.

Úttak

Fyrir hvert prófunartilvik skal prenta línu sem inniheldur $k$ fleytitölur aðskildar með bilum, hverja sniðna með nákvæmlega einum aukastaf, sem tákna mesta tíma í félagsskap fyrir hvern vin.

Dæmi

Inntak 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

Úttak 1

3.0 3.0
1.5 1.5
3.5 3.5 2.5

Athugasemd

Fyrir þriðja prófunartilvikið í sýnidæminu er fyrsti mögulegi fundartíminn í verslunarmiðstöðinni $5$ tímaeiningar.

• Vinirnir frá hnútum $1$ og $2$ geta hist á miðjum legg $(1, 2)$ eftir $1.5$ einingar, ferðast saman til baka í verslunarmiðstöðina á öðrum $1.5$ einingum og síðan beðið í $2$ einingar í verslunarmiðstöðinni, sem gerir samtals $3.5$ einingar í félagsskap.
• Vinurinn frá hnúti $3$ hittir vinina frá hnúti $1$ á miðjum legg $(1, 3)$ eftir $2.5$ einingar og snýr til baka með þeim á $2.5$ einingum, sem gerir samtals $2.5$ einingar í félagsskap.