Di sebuah kampus yang indah, Panda dan teman-temannya hendak berkumpul untuk makan bersama. Mereka senang menghabiskan waktu bersama di perjalanan karena bisa mengobrol dengan bebas satu sama lain.

Kampus tersebut dimodelkan sebagai graf tak berarah terhubung dengan $n$ simpul dan $m$ sisi yang memiliki panjang. Tempat pertemuan adalah mal, yang terletak di simpul $1$. Sebanyak $k$ teman berangkat dari simpul-simpul yang berbeda menuju mal. Semua teman bergerak dengan kecepatan yang sama ($1$ satuan jarak per satuan waktu), dan diperbolehkan mengubah arah di posisi mana pun di sepanjang sisi (lihat penjelasan contoh).

Misalkan $t_{\text{meet}}$ adalah waktu paling awal yang mungkin sehingga semua teman dapat mencapai mal selambat-lambatnya pada waktu tersebut. Berdasarkan waktu pertemuan paling awal ini, untuk masing-masing teman secara individual, carilah total waktu maksimum yang dapat mereka habiskan bersama teman lainnya (artinya setidaknya ada satu teman lain yang berada di lokasi yang persis sama pada graf, baik di sebuah simpul maupun di suatu posisi pada sisi) sebelum berkumpul seluruhnya di mal.

Saat meninjau seorang teman spesifik $i$, jalur dan strategi pergerakan dari semua teman lainnya $j \neq i$ dioptimalkan untuk memaksimalkan waktu kebersamaan bagi teman $i$, selama semua teman tiba di mal tidak lebih lambat dari $t_{\text{meet}}$.

Masukan

Baris pertama berisi sebuah bilangan bulat $T$ ($1 \le T \le 10^4$), yang menyatakan banyaknya kasus uji.

Untuk setiap kasus uji, baris pertama berisi tiga bilangan bulat $n, m, k$ ($2 \le n \le 3 \times 10^5$, $n - 1 \le m \le 10^6$, $2 \le k \le n$), yang masing-masing menyatakan banyaknya simpul, sisi, dan teman.

Baris kedua berisi $k$ bilangan bulat berbeda $a_1, a_2, \ldots, a_k$ ($1 \le a_i \le n$), yang menyatakan simpul awal dari masing-masing teman.

$m$ baris berikutnya masing-masing berisi tiga bilangan bulat $u, v, w$ ($1 \le u, v \le n$, $u \neq v$, $1 \le w \le 10^9$), yang menunjukkan sebuah sisi antara simpul $u$ dan $v$ dengan panjang $w$. Graf tersebut terhubung serta tidak memiliki sisi ganda maupun gelung (self-loop).

Jumlah $n$ di seluruh kasus uji tidak melebihi $3 \times 10^5$, dan jumlah $m$ di seluruh kasus uji tidak melebihi $10^6$.

Keluaran

Untuk setiap kasus uji, keluarkan satu baris berisi $k$ bilangan titik-ambang yang dipisahkan oleh spasi, masing-masing diformat hingga tepat satu angka di belakang koma, yang menyatakan waktu maksimum kebersamaan untuk setiap teman.

Contoh

Masukan 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

Keluaran 1

3.0 3.0
1.5 1.5
3.5 3.5 2.5

Catatan

Untuk kasus uji ketiga pada contoh, waktu pertemuan paling awal di mal adalah $5$ satuan waktu.

• Teman-teman dari simpul $1$ dan $2$ dapat bertemu di tengah sisi $(1, 2)$ dalam $1.5$ satuan waktu, berjalan bersama kembali ke mal dalam $1.5$ satuan waktu lagi, lalu menunggu $2$ satuan waktu di mal, sehingga menghasilkan total $3.5$ satuan waktu kebersamaan.
• Teman dari simpul $3$ bertemu dengan teman dari simpul $1$ di tengah sisi $(1, 3)$ dalam $2.5$ satuan waktu dan kembali bersama mereka dalam $2.5$ satuan waktu, sehingga menghasilkan total $2.5$ satuan waktu kebersamaan.