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

Agente 004

Por Thalyson Nepomuceno, Universidade Estadual do Ceará BR Brazil

Timelimit: 3

Uma organização criminosa da cidade está ficando mais poderosa a cada dia, e para tentar acompanhar esse avanço, a organização protetora da cidade está investindo muito no treinamento dos seus homens. Bino, também conhecido como Agente 004, é o melhor agente da organização protetora, então ele foi designado para uma missão especial.

A missão especial de Bino é entregar uma mensagem secreta de uma sede de treinamento de agentes especiais para outra. Porém a cidade está cheia de criminosos, e todos eles querem interceptar Bino na sua missão.

Bino não conhece muito bem as rotas da cidade, pois passou a maior parte do tempo de sua vida sendo treinado em campos especiais, diferentemente dos criminosos, que passam maior parte das suas vidas nas ruas, e conhecem todas as rotas possíveis.

Como Bino é o melhor agente do mundo, ele sabe que é capaz de eliminar qualquer quantidade de criminosos que estão no mesmo local dele instantaneamente. Os criminosos podem interceptar Bino em qualquer lugar da cidade(Em todas as rotas e em tudos os lugares, inclusive, nos lugares onde estão as sedes de treinamento inicial e a destino). Bino e os criminosos se deslocam com velocidade de 12 m/s. Bino sempre utiliza o caminho que encontrará menos criminosos, porém, os criminosos sempre utilizam os melhores caminhos para interceptar Bino.

Sua tarefa é descobrir qual a quantidade mínima de criminosos que Bino terá que eliminar para entregar uma mensagem secreta de uma sede de treinamento para outra. É garantindo que existirá um caminho entre qualquer lugar na cidade para qualquer outro lugar.

Entrada

A primeira linha contém 4 inteiros,  N(1 ≤ N ≤ 10000), C(1 ≤ C ≤ 50000), S(1 ≤ S ≤ 50000) e B (1 ≤ B ≤ 10000), representando respectivamente o número de lugares na cidade, o número de rotas conhecidas pelo Bino, o número de rotas conhecidas somente pelos criminosos  e o número de criminosos. Cada uma das próximas C linhas contém três inteiros a(1 ≤ aN), b(1 ≤ bN) e v(1 ≤ v ≤ 1000), representando que existe uma rota entre os lugares a e b com distância de v metros. Cada uma das próximas S linhas contém três inteiros a(1 ≤ aN), b(1 ≤ bN), v(1 ≤ v ≤ 1000), representando que existe uma rota secreta entre os lugares a e b com distância de v metros. A próxima linha contém B inteiros li(1 ≤ liN) representando que o criminoso i está inicialmente no lugar l. A última linha do caso de teste contém 2 inteiros K(1 ≤ K ≤ 10000),  e F(1 ≤ F ≤ 10000), representando respectivamente o lugar inicial do Bino e o lugar onde ele vai ter que entregar a mensagem secreta.

Saída

Imprima a quantidade mínima de criminosos que Bino vai eliminar no caminho.

Exemplo de Entrada Exemplo de Saída

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