Trong một khuôn viên trường tuyệt đẹp, Panda và những người bạn của mình đang hẹn nhau đi ăn. Họ rất thích dành thời gian bên nhau trên đường đi vì có thể thoải mái trò chuyện.

Khuôn viên trường được mô hình hóa như một đồ thị vô hướng liên thông gồm $n$ đỉnh và $m$ cạnh có độ dài. Điểm hẹn là trung tâm thương mại nằm ở đỉnh $1$. Có $k$ người bạn xuất phát từ các đỉnh phân biệt và di chuyển đến trung tâm thương mại. Tất cả những người bạn đều di chuyển với cùng một vận tốc ($1$ đơn vị khoảng cách trên mỗi đơn vị thời gian), và được phép đổi hướng tại bất kỳ vị trí nào trên cạnh (xem giải thích ví dụ).

Gọi $t_{\text{meet}}$ là thời điểm sớm nhất có thể sao cho tất cả những người bạn đều có thể đến được trung tâm thương mại muộn nhất vào thời điểm đó. Dựa trên thời điểm gặp nhau sớm nhất này, với mỗi người bạn riêng biệt, hãy tìm tổng thời gian tối đa mà họ có thể đi cùng bạn đồng hành (nghĩa là có ít nhất một người bạn khác ở cùng một vị trí chính xác trên đồ thị, có thể là một đỉnh hoặc một điểm nằm trên cạnh) trước khi tất cả tập hợp đầy đủ tại trung tâm thương mại.

Khi xét một người bạn cụ thể $i$, đường đi và chiến lược di chuyển của tất cả những người bạn khác $j \neq i$ được tối ưu hóa nhằm cực đại hóa thời gian có bạn đồng hành của người bạn $i$, miễn là tất cả mọi người đều đến trung tâm thương mại không muộn hơn $t_{\text{meet}}$.

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên $T$ ($1 \le T \le 10^4$), biểu thị số lượng bộ dữ liệu.

Với mỗi bộ dữ liệu, dòng đầu tiên chứa ba số nguyên $n, m, k$ ($2 \le n \le 3 \times 10^5$, $n - 1 \le m \le 10^6$, $2 \le k \le n$), lần lượt biểu thị số đỉnh, số cạnh và số người bạn.

Dòng thứ hai chứa $k$ số nguyên phân biệt $a_1, a_2, \ldots, a_k$ ($1 \le a_i \le n$), biểu thị các đỉnh xuất phát của những người bạn.

$m$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $u, v, w$ ($1 \le u, v \le n$, $u \neq v$, $1 \le w \le 10^9$), cho biết một cạnh nối giữa đỉnh $u$ và đỉnh $v$ có độ dài $w$. Đồ thị liên thông và không có cạnh bội hay khuyên.

Tổng của $n$ trong tất cả các bộ dữ liệu không vượt quá $3 \times 10^5$, và tổng của $m$ trong tất cả các bộ dữ liệu không vượt quá $10^6$.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra một dòng gồm $k$ số thực cách nhau bởi dấu cách, mỗi số được định dạng chính xác một chữ số sau dấu thập phân, biểu thị thời gian tối đa có bạn đồng hành của mỗi người bạn.

Ví dụ

Dữ liệu vào 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

Dữ liệu ra 1

3.0 3.0
1.5 1.5
3.5 3.5 2.5

Ghi chú

Đối với bộ dữ liệu thứ ba trong ví dụ, thời điểm gặp nhau sớm nhất tại trung tâm thương mại là $5$ đơn vị thời gian.

• Những người bạn xuất phát từ đỉnh $1$ và $2$ có thể gặp nhau ở chính giữa cạnh $(1, 2)$ sau $1.5$ đơn vị thời gian, cùng nhau quay lại trung tâm thương mại trong $1.5$ đơn vị thời gian nữa, rồi đợi $2$ đơn vị thời gian tại trung tâm thương mại, tổng cộng có $3.5$ đơn vị thời gian đồng hành.
• Người bạn xuất phát từ đỉnh $3$ gặp những người bạn từ đỉnh $1$ ở chính giữa cạnh $(1, 3)$ sau $2.5$ đơn vị thời gian và cùng họ quay về trong $2.5$ đơn vị thời gian, tổng cộng có $2.5$ đơn vị thời gian đồng hành.