وصف المسألة

توجد في مملكة 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$، لا يوجد طريقان ($2$) أو أكثر يربطان بين $p$ و$q$. ويمكن الانتقال من أي مدينة إلى أي مدينة أخرى عبر سلوك بعض الطرق.
• تمثل الأسطر الـ $K$ التالية معلومات مراكز التسوق. يحتوي السطر $(i + M + 1)$ ($1 \le i \le K$) على عدد صحيح $1$ هو $s_i$ ($1 \le s_i \le N$). وهذا يعني أنه يوجد مركز تسوق في المدينة $s_i$. لا تتكرر نفس القيمة مرتين ($2$) أو أكثر بين $s_1, \dots, s_K$.

الإخراج

اطبع إلى الإخراج القياسي عددًا صحيحًا واحدًا ($1$) يمثل القيمة العظمى لأقصر مسافة إلى مدينة بها مركز تسوق بعد تقريب الأجزاء العشرية إلى أقرب عدد صحيح.

مثال

مثال 1

الإدخال

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

الإخراج

2

التوضيح

يمثل المثال $1$ المدن الموضحة في الشكل أدناه. أطوال جميع الطرق تساوي $1$. ولا يوجد مركز تسوق إلا في المدينة $1$.

أبعد نقطة عن مدينة بها مركز تسوق هي النقطة الواقعة على الطريق الرابط بين المدينة $2$ والمدينة $3$ على بُعد $0.5$ من المدينة $2$، والمسافة منها إلى المدينة التي بها مركز تسوق تساوي $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$.