ในวิทยาเขตที่สวยงาม Panda และเพื่อนๆ กำลังนัดเจอกันเพื่อรับประทานอาหาร พวกเขาชอบใช้เวลาร่วมกันระหว่างเดินทาง เพราะจะได้พูดคุยกันได้อย่างอิสระ

วิทยาเขตถูกจำลองเป็นกราฟไม่มีทิศทางที่เชื่อมต่อกัน มี $n$ โหนด และมีเส้นเชื่อม $m$ เส้นที่ระบุความยาว จุดนัดพบคือห้างสรรพสินค้าซึ่งตั้งอยู่ที่โหนด $1$ มีเพื่อน $k$ คนเริ่มต้นเดินทางจากโหนดที่แตกต่างกันไปยังห้างสรรพสินค้า เพื่อนทุกคนเคลื่อนที่ด้วยความเร็วเท่ากัน (ระยะทาง $1$ หน่วยต่อหนึ่งหน่วยเวลา) และสามารถเปลี่ยนทิศทางได้ทุกตำแหน่งบนเส้นเชื่อม (ดูคำอธิบายตัวอย่างประกอบ)

ให้ $t_{\text{meet}}$ เป็นเวลาที่เร็วที่สุดที่เป็นไปได้ซึ่งเพื่อนทุกคนสามารถเดินทางไปถึงห้างสรรพสินค้าได้ทันเวลานั้น จากเวลานัดพบที่เร็วที่สุดนี้ สำหรับเพื่อนแต่ละคนแยกกัน จงหาเวลาสะสมสูงสุดที่เขาสามารถอยู่ร่วมกับเพื่อนคนอื่น (หมายถึงมีเพื่อนคนอื่นอย่างน้อยหนึ่งคนอยู่ที่ตำแหน่งเดียวกันบนกราฟพอดี ซึ่งอาจเป็นโหนดหรือตำแหน่งหนึ่งบนเส้นเชื่อมก็ได้) ก่อนที่ทุกคนจะมารวมตัวกันครบที่ห้างสรรพสินค้า

เมื่อพิจารณาเพื่อนคนที่ $i$ เส้นทางและกลยุทธ์การเคลื่อนที่ของเพื่อนคนอื่นๆ ทั้งหมด $j \neq i$ จะถูกปรับให้เหมาะสมที่สุดเพื่อเพิ่มเวลาการมีเพื่อนร่วมทางของเพื่อนคนที่ $i$ ให้มากที่สุด ตราบใดที่เพื่อนทุกคนมาถึงห้างสรรพสินค้าไม่ช้ากว่า $t_{\text{meet}}$

ข้อมูลนำเข้า

บรรทัดแรกประกอบด้วยจำนวนเต็ม $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$ ตัวคั่นด้วยช่องว่าง โดยแต่ละตัวจัดรูปแบบให้มีทศนิยมหนึ่งตำแหน่งพอดี แทนเวลาสูงสุดที่เพื่อนแต่ละคนมีเพื่อนร่วมทาง

ตัวอย่าง

ข้อมูลนำเข้า 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

ข้อมูลส่งออก 1

3.0 3.0
1.5 1.5
3.5 3.5 2.5

หมายเหตุ

สำหรับกรณีทดสอบที่สามในตัวอย่าง เวลานัดพบที่เร็วที่สุดที่ห้างสรรพสินค้าคือ $5$ หน่วยเวลา

• เพื่อนจากโหนด $1$ และ $2$ สามารถพบกันที่กึ่งกลางของเส้นเชื่อม $(1, 2)$ ในเวลา $1.5$ หน่วย เดินทางกลับไปที่ห้างสรรพสินค้าด้วยกันในเวลาอีก $1.5$ หน่วย แล้วรออยู่ที่ห้างสรรพสินค้าอีก $2$ หน่วย รวมเป็นเวลาที่อยู่ด้วยกันทั้งหมด $3.5$ หน่วย
• เพื่อนจากโหนด $3$ พบกับเพื่อนจากโหนด $1$ ที่กึ่งกลางของเส้นเชื่อม $(1, 3)$ ในเวลา $2.5$ หน่วย และเดินทางกลับมาพร้อมกันในเวลา $2.5$ หน่วย รวมเป็นเวลาที่อยู่ด้วยกันทั้งหมด $2.5$ หน่วย