תיאור הבעיה

בממלכת 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$.