URI Online Judge | 1806 | [P2][Univ]

Agent 004

By Thalyson Nepomuceno, Universidade Estadual do Ceará BR Brazil

Timelimit: 3

A criminal organization of the city is getting more powerful every day, and for to try follow this advance, the protective organization of the city is investing heavily on the training of his men. Bino, also known as Agent 004, is the best agent of the protective organization, thus he was assigned to a special mission.

The special mission of Bino is to deliver a secret message from a barrack of training special agents to another barracks. The city is full of criminals, and they want to intercept Bino before to deliver the secret message.

Bino not know very well the routes of the city, having spent most of the time of your life being trained in barracks of training special, unlike the criminals, who spend most of their lives on the streets and know all possible routes.

As Bino is the world's best agent, he is capable of instantly eliminating any number of criminals. Criminals can intercept Bino anywhere in the city (In all routes and all  places, even in places where the initial barrack and the destination barrack). Bino and criminals move at 12 m/s. Bino always use the path that will find less criminals, but criminals always use the best paths to intercept Bino.

Your task is to find out what the minimum amount of criminals who Bino will have to eliminate to deliver a secret message from a barrack of training to another. It is guaranteed there will still be at least one path from every place in town for every other place.

Input

The first line contains four integers, N(1 ≤ N ≤ 10000), C(1 ≤ C ≤ 50000), S(1 ≤ S ≤ 50000) and B(1 ≤ B ≤ 10000), representing respectively the number of places in the city, the number of routes known by Bino, the number of routes known only by criminals and the number of criminals. Each of the next C lines contains three integers a(1 ≤ aN), b(1 ≤ bN) and v (1 ≤ v1000), representing that there is a route between locations a and b with distance v meters. Each of the next lines S contains three integers a(1 ≤ aN), b(1 ≤ bN), v(1 ≤ v ≤ 1000) representing that there is a secret route between locations a and b with distance v meters. The next line contains B integers li (1 ≤ liN) representing the criminal i starts in place l. The last test case line contains two integer K(1 ≤ KN), and F(1 ≤ FN), respectively representing the initial place Bino and where he'll have to deliver a secret message.

Output

Print the minimum amount of criminals who Bino will eliminate.

Input Sample Output Sample

6 5 0 3
2 1 10
2 4 5
4 3 5
5 4 5
6 4 6
3 6 5
3 2

2

6 5 1 3
2 1 10
2 4 5
4 3 5
5 4 5
6 4 6
6 4 5
3 6 5
3 2

3