FiFo | RoAlgo Educational Contest #1 | Peridea

Task

You are on the planet Peridea with Ahsoka, Ezra and Huyang.
They want to escape the planet, but because of the Jedi legend surrounding it, no outside force can help them. What's more, the Nightsisters have put a curse on them, making it impossible to escape undetected.
Searching for a solution, Ezra discovered a weakness in the curse. If they manage to obtain an ancient code and disable a series of magical symbols, they will be able to deactivate the curse and have a chance to escape undetected, thus succeeding in stopping the operation to rebuild the Dark Empire.
You are given $N$ ancient artifacts, any $2$ having a direct or indirect path, each path having a specific decryption cost. Each path, after you've traveled it, will change its decryption code, so if you want to go through that path again, you'll have to decrypt it. The decryption cost for a road remains the original cost. To undo the curse, you must obtain the $K$ demonic artifacts.
Beyond that, you can only move between neighboring artifacts and with a direct path. You already have an artifact, so you have a chance to escape. In addition, Huyang has a magic power, so you can still move between two artifacts that are not neighbors with a known decryption cost. Unfortunately you're limited to $LIM$ accesses to Huyang's power, so the Nightsisters will track you down.
Find the minimum decryption time from the source artifact, to the destination artifact, getting the $K$ demon artifacts. The galaxy depends on you.

Input data

On the first line are five integers, $N, M, T, K$ and $LIM$, where $N$ is the number of artifacts, $M$ is the number of paths between artifacts, $T$ is the number of paths you can travel with Huyang, $K$ is the number of demonic artifacts, and $LIM$ is the maximum number of uses of Huyang's magic powers.
On the next $M$ lines will be three numbers: $u,v,w$; $u$ and $v$ being the artifacts that have direct path, respectively $w$ - the decryption cost.
On the next $T$ lines will be three numbers: $u,v,w$; $u$ and $v$ being the artifacts that have direct path using Huyang, and $w$ - the decryption cost.
On the next line are $K$ numbers, representing the $K$ demon artifacts.
On the last line are $2$ numbers: $src, dest$, where $src$ represents the artifact you have, respectively $dest$ the final artifact for releasing the curse.

Output data

You will display the minimum time to break the curse, so you can stop the Dark Empire's rebuilding operation.

Constraints and clarifications

• $1 \leq N \leq 5 \ 000$
• $1 \leq M \leq N \cdot (N-1) / 2$
• $0 \leq K \leq 15$
• $0 \leq T \leq N$
• $0 \leq LIM \leq 9$
• $1 \leq decryption \ time \leq 100$

Comment

Due to the very large input data, we recommend using the following lines at the beginning of the main() function in the C++ program:

ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);

Example 1

stdin

5 5 1 1 1
1 2 2
2 3 100
2 4 5
3 5 2
4 5 2
1 3 0
3
1 5

stdout

2

As can be seen from the above image, the shortest path is: $1 \rightarrow 3 \rightarrow 5$, with total decoding time equal to $2$.