相約聚餐 - Problème

在美麗的校園裡，Panda 和他的朋友們正相約一起去吃飯。他們非常享受在路途上相處的時光，因為彼此可以暢所欲言地聊天。

校園被建模為一張包含 $n$ 個節點與 $m$ 條帶權邊的連通無向圖。集合地點是位於節點 $1$ 的商場。共有 $k$ 位朋友從不同的節點出發前往商場。所有朋友皆以相同的速度移動（每單位時間移動 $1$ 單位距離），且允許在邊上的任意位置改變移動方向（請見範例說明）。

令 $t_{\text{meet}}$ 為所有朋友皆能在該時間點之前抵達商場的最早可能時間。基於這個最早可能集合時間，請針對每位朋友個別求出：在最終全員於商場會合之前，他最多能有多少總時間是有同伴陪伴的（意即至少有另一位朋友與他處於圖上完全相同的位置，可以是某個節點或某條邊上的某個位置）。

當考慮某位特定朋友 $i$ 時，只要所有朋友皆不晚於 $t_{\text{meet}}$ 抵達商場，所有其他朋友 $j \neq i$ 的路徑與移動策略都會為了最大化朋友 $i$ 的陪伴時間而進行最佳化。

第一行包含一個整數 $T$ ($1 \le T \le 10^4$)，代表測試資料的組數。

對於每組測試資料，第一行包含三個整數 $n, m, k$ ($2 \le n \le 3 \times 10^5$, $n - 1 \le m \le 10^6$, $2 \le k \le n$)，分別代表節點數、邊數與朋友人數。

第二行包含 $k$ 個相異整數 $a_1, a_2, \ldots, a_k$ ($1 \le a_i \le n$)，代表各位朋友的起始節點。

接下來的 $m$ 行，每行包含三個整數 $u, v, w$ ($1 \le u, v \le n$, $u \neq v$, $1 \le w \le 10^9$)，表示節點 $u$ 與節點 $v$ 之間有一條長度為 $w$ 的邊。保證圖是連通的，且沒有重邊或自環。

所有測試資料中 $n$ 的總和不超過 $3 \times 10^5$，$m$ 的總和不超過 $10^6$。

對於每組測試資料，輸出一行包含 $k$ 個以空格分隔的浮點數，每個數皆格式化為恰好一位小數，代表每位朋友有人陪伴的最大時間。

3.0 3.0
1.5 1.5
3.5 3.5 2.5

對於範例中的第三組測試資料，在商場集合的最早時間為 $5$ 單位時間。

來自節點 $1$ 與節點 $2$ 的朋友可以在 $1.5$ 單位時間後於邊 $(1, 2)$ 的中點相遇，再花 $1.5$ 單位時間一起走回商場，接著在商場等待 $2$ 單位時間，總共獲得 $3.5$ 單位時間的陪伴。
來自節點 $3$ 的朋友在 $2.5$ 單位時間後於邊 $(1, 3)$ 的中點與來自節點 $1$ 的朋友相遇，並花 $2.5$ 單位時間與其一同返回，總共獲得 $2.5$ 單位時間的陪伴。

QOJ.ac