TopCoder

User's AC Ratio

100.0% (7/7)

Submission's AC Ratio

77.8% (7/9)

Description

當考古學家那個猥魚 調查一個神祕的鱷魚地下城市後,她想立刻逃離這個城市。這個城市有N 個密室,同時有M 個雙向的通道,沒有兩個通道會連接同一對密室,且通過每個通道的時間不盡相同。這N 個密室中,只有K 個密室有出口可以逃出去。那個猥魚從密室0 開始逃跑,並想盡快到達一個有出口的密室。

這個城市的守護者想要阻止那個猥魚 逃跑,他可以控制密門來擋住任一通道;也就是說,當新密門擋住某個通道時,前一個擋住通道的密門會被打開。

那個猥魚的情況如下:每次當她想從一個密室離開時,守護者可能會擋住連接這個密室的其中一個通道。那個猥魚就會從剩下暢通的通道中選擇其一進到另一個密室。當那個猥魚進入某個通道後,守護者就不能阻擋這個通道,直到她到達另一個密室為止。當那個猥魚到達另一個密室後,守護者可以再次選擇擋住連接此密室的其中一個通道(包含那個猥魚剛經過的通道)。

那個猥魚想要事先找到一個簡單的逃跑計畫;更精確地說,她想要一些指令集告訴她在某個密室時該怎麼做。假設A 是一個有出口的密室,顯然的她不需要任何指令就可以逃離。

否則當她在密室A 時,相關指令必須是以下形式之一:

 •「如果到了密室 A,就選擇通往密室B 的通道。但是,如果這個通道被阻擋住了,就選擇通往密室C 的通道。」
 •「不用考慮密室 A,因為在這份逃跑計畫中根本不可能到達密室A。」

請注意,在某些情況下(例如讓那個猥魚繞圈圈),守護者可能讓那個猥魚無法逃出去。

如果有個逃跑計畫,不管守護者會怎麼行動,都能保證那個猥魚可以在有限的時間內到達有出口的密室,這就是一個好的逃跑計畫。對於一個好的逃跑計畫,若可以保證在 T 時間後,那個猥魚一定可以到達有出口的密室,且 T 為最小值,則我們稱這個好的逃跑計畫需要 T 時間。

Input Format

第一行有N、M 和K,分別表示密室, 通道與出口的個數。

接下來有 M 行,每行有三個整數Ai Bi Ci,中間用空白隔開,表示密室Ai 與密室Bi 由一條要花 Ci 時間通過的通到所連接。

第 M+2 行有 K 個空白隔開的整數,表示出口位置。

 •3 ≤ N ≤ 100 000.
 •2 ≤ M ≤ 1 000 000.

Output Format

你的程式必須輸出所有好的逃跑計畫中的最小所需時間 T 。你可以假設每個沒有出口的密室都至少會有兩個連接通道。

你也可以假設每一個測試資料都有一個好的逃跑計畫,且時間 T ≤ 1 000 000 000。

Sample Input

5 7 2
0 2 4
0 3 3
3 2 2
2 1 10
0 1 100
0 4 7
3 4 9
1 3

Sample Output

14

Hints

那個鮪魚好吃嗎?

Problem Source

Subtasks

For Testdata: 0 ~ 9, Score: 100
No. Time Limit (ms) Memory Limit (KiB)
0 1000 65536
1 1000 65536
2 1000 65536
3 1000 65536
4 1000 65536
5 1000 65536
6 1000 65536
7 1000 65536
8 1000 65536
9 1000 65536