In uno splendido campus, Panda e i suoi amici si stanno incontrando per mangiare insieme. Amano trascorrere del tempo in compagnia lungo il tragitto, perché possono chiacchierare liberamente tra loro.

Il campus è modellato come un grafo connesso non orientato con $n$ nodi e $m$ archi dotati di lunghezza. Il punto di ritrovo è il centro commerciale, situato nel nodo $1$. $k$ amici partono da nodi distinti e si dirigono verso il centro commerciale. Tutti gli amici si muovono alla stessa velocità ($1$ unità di distanza per unità di tempo) e possono cambiare direzione in qualsiasi posizione lungo un arco (vedi la spiegazione dell'esempio).

Sia $t_{\text{meet}}$ il minimo istante di tempo possibile entro il quale tutti gli amici possono raggiungere il centro commerciale. Sulla base di questo tempo minimo di ritrovo, per ciascun amico singolarmente, trova il tempo totale massimo che può trascorrere in compagnia (cioè con almeno un altro amico esattamente nella stessa posizione sul grafo, che può essere un nodo o un punto lungo un arco) prima del raduno finale al centro commerciale.

Quando si considera uno specifico amico $i$, i percorsi e le strategie di movimento di tutti gli altri amici $j \neq i$ vengono ottimizzati per massimizzare il tempo in compagnia dell'amico $i$, purché tutti gli amici arrivino al centro commerciale non oltre l'istante $t_{\text{meet}}$.

Input

La prima riga contiene un intero $T$ ($1 \le T \le 10^4$), che indica il numero di casi di test.

Per ogni caso di test, la prima riga contiene tre interi $n, m, k$ ($2 \le n \le 3 \times 10^5$, $n - 1 \le m \le 10^6$, $2 \le k \le n$), che rappresentano rispettivamente il numero di nodi, di archi e di amici.

La seconda riga contiene $k$ interi distinti $a_1, a_2, \ldots, a_k$ ($1 \le a_i \le n$), che indicano i nodi di partenza degli amici.

Le successive $m$ righe contengono ciascuna tre interi $u, v, w$ ($1 \le u, v \le n$, $u \neq v$, $1 \le w \le 10^9$), che indicano un arco tra il nodo $u$ e il nodo $v$ di lunghezza $w$. Il grafo è connesso e non ha archi multipli né cappi.

La somma di $n$ su tutti i casi di test non supera $3 \times 10^5$, e la somma di $m$ su tutti i casi di test non supera $10^6$.

Output

Per ogni caso di test, stampa una riga contenente $k$ numeri in virgola mobile separati da spazi, ciascuno formattato con esattamente una cifra decimale, che rappresentano il tempo massimo trascorso in compagnia per ciascun amico.

Esempi

Input 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

Output 1

3.0 3.0
1.5 1.5
3.5 3.5 2.5

Nota

Per il terzo caso di test nell'esempio, il tempo minimo di ritrovo al centro commerciale è di $5$ unità di tempo.

• Gli amici dei nodi $1$ e $2$ possono incontrarsi a metà dell'arco $(1, 2)$ in $1.5$ unità, tornare insieme al centro commerciale in altre $1.5$ unità e poi attendere $2$ unità al centro commerciale, per un totale di $3.5$ unità di compagnia.
• L'amico del nodo $3$ incontra gli amici del nodo $1$ a metà dell'arco $(1, 3)$ in $2.5$ unità e ritorna con loro in $2.5$ unità, per un totale di $2.5$ unità di compagnia.