Sur un magnifique campus, Panda et ses amis se retrouvent pour partager un repas. Ils aiment passer du temps ensemble en chemin, car cela leur permet de discuter librement.

Le campus est modélisé par un graphe non orienté connexe comportant $n$ nœuds et $m$ arêtes pondérées par leur longueur. Le lieu de rendez-vous est le centre commercial, situé au nœud $1$. $k$ amis partent de nœuds distincts et se dirigent vers le centre commercial. Tous les amis se déplacent à la même vitesse ($1$ unité de distance par unité de temps) et sont autorisés à changer de direction en n'importe quelle position le long d'une arête (voir l'explication de l'exemple).

Soit $t_{\text{meet}}$ la date au plus tôt à laquelle tous les amis peuvent avoir rejoint le centre commercial. En se basant sur ce temps de rassemblement au plus tôt, trouvez pour chaque ami individuellement la durée totale maximale qu'il peut passer en compagnie d'autres amis (c'est-à-dire qu'au moins un autre ami se trouve exactement au même endroit sur le graphe, que ce soit un nœud ou une position le long d'une arête) avant le rassemblement final au centre commercial.

Lorsqu'on considère un ami particulier $i$, les trajets et stratégies de déplacement de tous les autres amis $j \neq i$ sont optimisés afin de maximiser le temps passé en compagnie pour l'ami $i$, tant que tous les amis arrivent au centre commercial au plus tard à l'instant $t_{\text{meet}}$.

Entrée

La première ligne contient un entier $T$ ($1 \le T \le 10^4$), désignant le nombre de cas de test.

Pour chaque cas de test, la première ligne contient trois entiers $n, m, k$ ($2 \le n \le 3 \times 10^5$, $n - 1 \le m \le 10^6$, $2 \le k \le n$), représentant respectivement le nombre de nœuds, d'arêtes et d'amis.

La deuxième ligne contient $k$ entiers distincts $a_1, a_2, \ldots, a_k$ ($1 \le a_i \le n$), désignant les nœuds de départ des amis.

Les $m$ lignes suivantes contiennent chacune trois entiers $u, v, w$ ($1 \le u, v \le n$, $u \neq v$, $1 \le w \le 10^9$), indiquant une arête entre les nœuds $u$ et $v$ de longueur $w$. Le graphe est connexe et ne comporte ni arêtes multiples ni boucles.

La somme de $n$ sur l'ensemble des cas de test ne dépasse pas $3 \times 10^5$, et la somme de $m$ sur l'ensemble des cas de test ne dépasse pas $10^6$.

Sortie

Pour chaque cas de test, affichez une ligne contenant $k$ nombres à virgule flottante séparés par des espaces, chacun formaté avec exactement un chiffre après la virgule, représentant le temps maximal passé en compagnie pour chaque ami.

Exemples

Entrée 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

Sortie 1

3.0 3.0
1.5 1.5
3.5 3.5 2.5

Remarque

Pour le troisième cas de test de l'exemple, l'heure de rassemblement au plus tôt au centre commercial est de $5$ unités de temps.

• Les amis partant des nœuds $1$ et $2$ peuvent se rejoindre au milieu de l'arête $(1, 2)$ en $1.5$ unité de temps, revenir ensemble au centre commercial en $1.5$ unité supplémentaire, puis attendre $2$ unités au centre commercial, totalisant $3.5$ unités de compagnie.
• L'ami partant du nœud $3$ rejoint les amis du nœud $1$ au milieu de l'arête $(1, 3)$ en $2.5$ unités de temps et revient avec eux en $2.5$ unités, totalisant $2.5$ unités de compagnie.