Есептің шарты

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$ орындалады.