รายละเอียดโจทย์

ในอาณาจักร JOI มีเมืองอยู่ $N$ เมือง ซึ่งเชื่อมต่อกันด้วยถนนที่สัญจรได้สองทิศทางจำนวน $M$ สาย มีห้างสรรพสินค้าตั้งอยู่ใน $K$ เมือง และประชาชนจะเดินทางไปตามถนนเพื่อไปยังเมืองใดเมืองหนึ่งในนั้นเพื่อซื้อของ

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

เมื่อกำหนดข้อมูลของถนนและข้อมูลของเมืองที่มีห้างสรรพสินค้า จงเขียนโปรแกรมเพื่อหาระยะทางจากเมืองที่มีห้างสรรพสินค้าไปยังจุดบนถนนที่อยู่ไกลที่สุด (รวมถึงจุดปลายของถนนด้วย) ทั้งนี้สามารถละเว้นระยะทางที่ใช้ในการเดินทางภายในเมืองได้

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

อ่านข้อมูลนำเข้าต่อไปนี้จากข้อมูลนำเข้ามาตรฐาน:

• บรรทัดที่ $1$ มีจำนวนเต็ม $N, M, K$ คั่นด้วยช่องว่าง โดย $N$ แทนจำนวนเมืองในอาณาจักร JOI, $M$ แทนจำนวนถนนในอาณาจักร JOI และ $K$ แทนจำนวนเมืองที่มีห้างสรรพสินค้า ตามลำดับ เมืองทั้งหลายจะมีหมายเลขกำกับเป็น $1, 2, \dots, N$
• อีก $M$ บรรทัดถัดมาแทนข้อมูลของถนน บรรทัดที่ $(i + 1)$ ($1 \le i \le M$) มีจำนวนเต็ม $a_i, b_i, l_i$ ($1 \le a_i \le N, 1 \le b_i \le N, 1 \le l_i \le 1000$) คั่นด้วยช่องว่าง หมายความว่าถนนสายที่ $i$ เชื่อมระหว่างเมือง $a_i$ กับเมือง $b_i$ และมีความยาว $l_i$ ปลายทั้งสองด้านของถนนจะไม่เป็นเมืองเดียวกัน และสำหรับเมือง $2$ เมือง $p, q$ ใดๆ จะไม่มีถนนที่เชื่อมระหว่าง $p$ กับ $q$ ตั้งแต่ $2$ สายขึ้นไป นอกจากนี้ยังสามารถเดินทางจากเมืองใดๆ ไปยังเมืองใดๆ โดยไปตามถนนบางสายได้เสมอ
• อีก $K$ บรรทัดถัดมาแทนข้อมูลของห้างสรรพสินค้า บรรทัดที่ $(i + M + 1)$ ($1 \le i \le K$) มีจำนวนเต็ม $1$ จำนวนคือ $s_i$ ($1 \le s_i \le N$) หมายความว่าที่เมือง $s_i$ มีห้างสรรพสินค้า ในหมู่ $s_1, \dots, s_K$ จะไม่มีค่าที่ซ้ำกันปรากฏตั้งแต่ $2$ ครั้งขึ้นไป

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

แสดงจำนวนเต็ม $1$ จำนวนออกทางข้อมูลส่งออกมาตรฐาน คือค่าสูงสุดของระยะทางที่สั้นที่สุดไปยังเมืองที่มีห้างสรรพสินค้า โดยปัดเศษทศนิยมให้เป็นจำนวนเต็ม

ตัวอย่าง

ตัวอย่าง 1

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

3 3 1
1 2 1
2 3 1
3 1 1
1

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

2

คำอธิบาย

ตัวอย่างข้อมูลนำเข้าที่ $1$ แสดงเมืองดังรูปด้านล่าง ความยาวของถนนทุกสายเป็น $1$ และมีห้างสรรพสินค้าอยู่ที่เมือง $1$ เท่านั้น

จุดที่อยู่ไกลจากเมืองที่มีห้างสรรพสินค้ามากที่สุด คือจุดบนถนนที่เชื่อมระหว่างเมือง $2$ กับเมือง $3$ ณ ตำแหน่งที่ห่างจากเมือง $2$ เป็นระยะทาง $0.5$ ซึ่งมีระยะทางไปยังเมืองที่มีห้างสรรพสินค้าเท่ากับ $1.5$ ดังนั้นจึงแสดงผลเป็น $2$ ซึ่งเป็นค่าที่ปัดเศษแล้ว

ตัวอย่าง 2

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

4 5 2
1 2 4
1 3 1
2 3 2
2 4 2
3 4 1
2
4

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

3

ขอบเขตข้อมูล

• $2 \le N \le 3000$: จำนวนเมืองในอาณาจักร JOI
• $1 \le M \le 100000 = 10^5$: จำนวนถนนในอาณาจักร JOI
• $1 \le K \le N$: จำนวนเมืองที่มีห้างสรรพสินค้า
• $1 \le l_i \le 1000$: ความยาวของถนนสายที่ $i$

เกณฑ์การให้คะแนน

• สำหรับข้อมูลที่ใช้ตรวจส่วนที่มีคะแนนคิดเป็น $40\%$ ของคะแนนทั้งหมด จะสอดคล้องกับ $K = 1$