Na pięknym kampusie Panda i jego przyjaciele umawiają się na wspólny posiłek. Lubią spędzać razem czas po drodze, ponieważ mogą wtedy swobodnie ze sobą rozmawiać.

Kampus jest zamodelowany jako spójny graf nieskierowany o $n$ wierzchołkach i $m$ krawędziach mających długości. Miejscem spotkania jest centrum handlowe znajdujące się w wierzchołku $1$. $k$ przyjaciół wyrusza z parami różnych wierzchołków i zmierza do centrum handlowego. Wszyscy przyjaciele poruszają się z taką samą prędkością ($1$ jednostka odległości na jednostkę czasu) i mogą zmieniać kierunek ruchu w dowolnym miejscu na krawędzi (zobacz wyjaśnienie przykładu).

Niech $t_{\text{meet}}$ oznacza najwcześniejszy możliwy moment, w którym wszyscy przyjaciele mogą dotrzeć do centrum handlowego. Bazując na tym najwcześniejszym możliwym czasie spotkania, dla każdego przyjaciela z osobna wyznacz maksymalny łączny czas, jaki może on spędzić w towarzystwie (co oznacza, że co najmniej jeden inny przyjaciel znajduje się dokładnie w tym samym miejscu w grafie — w wierzchołku lub w pewnym punkcie na krawędzi) przed ostatecznym zebraniem się wszystkich w centrum handlowym.

Gdy rozważamy konkretnego przyjaciela $i$, ścieżki oraz strategie poruszania się wszystkich pozostałych przyjaciół $j \neq i$ są optymalizowane tak, aby zmaksymalizować czas spędzony w towarzystwie przez przyjaciela $i$, pod warunkiem że wszyscy przyjaciele dotrą do centrum handlowego nie później niż w chwili $t_{\text{meet}}$.

Wejście

Pierwszy wiersz zawiera liczbę całkowitą $T$ ($1 \le T \le 10^4$), oznaczającą liczbę przypadków testowych.

Dla każdego przypadku testowego pierwszy wiersz zawiera trzy liczby całkowite $n, m, k$ ($2 \le n \le 3 \times 10^5$, $n - 1 \le m \le 10^6$, $2 \le k \le n$), oznaczające odpowiednio liczbę wierzchołków, krawędzi oraz przyjaciół.

Drugi wiersz zawiera $k$ parami różnych liczb całkowitych $a_1, a_2, \ldots, a_k$ ($1 \le a_i \le n$), oznaczających wierzchołki startowe przyjaciół.

Kolejne $m$ wierszy zawiera po trzy liczby całkowite $u, v, w$ ($1 \le u, v \le n$, $u \neq v$, $1 \le w \le 10^9$), oznaczające krawędź między wierzchołkami $u$ oraz $v$ o długości $w$. Graf jest spójny i nie zawiera krawędzi wielokrotnych ani pętli.

Suma $n$ po wszystkich przypadkach testowych nie przekracza $3 \times 10^5$, a suma $m$ po wszystkich przypadkach testowych nie przekracza $10^6$.

Wyjście

Dla każdego przypadku testowego wypisz jeden wiersz zawierający $k$ liczb zmiennoprzecinkowych oddzielonych spacjami, każdą sformatowaną z dokładnie jednym miejscem po przecinku, oznaczających maksymalny czas w towarzystwie dla każdego przyjaciela.

Przykład

Wejście 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

Wyjście 1

3.0 3.0
1.5 1.5
3.5 3.5 2.5

Uwagi

W trzecim przypadku testowym z przykładu najwcześniejszy czas spotkania w centrum handlowym wynosi $5$ jednostek czasu.

• Przyjaciele z wierzchołków $1$ oraz $2$ mogą spotkać się w połowie krawędzi $(1, 2)$ po $1.5$ jednostki czasu, wrócić razem do centrum handlowego w kolejne $1.5$ jednostki, a następnie zaczekać $2$ jednostki w centrum handlowym, co daje łącznie $3.5$ jednostki czasu w towarzystwie.
• Przyjaciel z wierzchołka $3$ spotyka przyjaciół z wierzchołka $1$ w połowie krawędzi $(1, 3)$ po $2.5$ jednostki czasu i wraca z nimi w $2.5$ jednostki, co daje łącznie $2.5$ jednostki czasu w towarzystwie.