Usina
A Usina Nuclear Indiscutivelmente Campeã (Unicamp) é organizada em N salas numeradas de 1 a N.
Por questões de segurança, o reator fica no subsolo, na sala de número N, e é monitorado por um técnico.
No passado, a sala de controle ficava logo ao lado do reator, mas os engenheiros estavam desconfortáveis no subsolo
e queriam uma sala em um lugar alto, para corresponder à sua importância. Agora, a sala de comando fica em um dos andares mais altos
da torre mais alta da usina, na sala de número 1, e os engenheiros se comunicam com o técnico por um telefone, caso detectem algum problema. Além disso, a
administração da Unicamp faz o possível para deixar a empresa mais divertida, como é a tendência de grandes empresas atuais. Por isso,
foram instalados escorregadores entre algumas salas. Evidentemente, só é possível ir de escorregador para uma sala que fique em uma altitude menor.
Um grave problema no reator foi detectado pelos engenheiros, mas o técnico responsável pelo reator desligou o telefone para dormir e é só
questão de tempo até que o reator exploda. Os engenheiros decidiram então sair correndo, ou melhor, escorregando para tentar avisar o técnico. Além
dos engenheiros, existem diversas pessoas na empresa espalhadas pelas salas. Os engenheiros vão descer pelos escorregadores a uma velocidade
de 1 metro por segundo e vão gritar alertas o tempo todo. Dentro de uma mesma sala o som se propaga perfeitamente (e, podemos considerar, instantaneamente).
Nos escorregadores, o grito de uma pessoa pode ser ouvido a uma distância de K metros (considere, também, instantaneamente).
Note que o som pode se propagar por uma sequência de salas e escorregadores enquanto a soma total da distância nos escorregadores for menor ou igual a K metros).
No entanto, como os gerentes da Unicamp não gostam de ouvir o barulho operacional da usina, há um isolamento sonoro no prédio que só permite que
o som se propague de andares mais altos para andares mais baixos, e não na direção contrária. Qualquer pessoa que ouça outra
pessoa gritando vai perceber o perigo e também vai começar a instantaneamente a gritar e usar os escorregadores para avisar os outros.
Você vai receber uma descrição da usina, com o número de salas, a quantidade de escorregadores e a descrição de cada escorregador.
Além disso, vai receber o número de salas que contém pessoas, quais salas contém
pessoas e a distância na qual as pessoas conseguem ser ouvidas nos escorregadores. A crise estará resolvida
quando alguma pessoa chegar perto o suficiente do técnico para que ele ouça os gritos, acorde e desligue o reator. Sua tarefa é calcular
o menor tempo necessário para que alguma pessoa avise o técnico e previna o desastre, ou indicar que isso não é possível com os escorregadores disponíveis.
Entrada
A primeira linha da entrada contém quatro inteiros
N, M, C e K, respectivamente o número de salas, o número de escorregadores, o número de salas que contém pessoas e a distância na qual as pessoas conseguem ser ouvidas.
As salas são identificadas por números de 1 a N. Os engenheiros sempre partem
da sala de número 1 e o técnico sempre está na sala de número N.
A segunda linha contém
C inteiros, P_1, P_2, ... P_C, indicando os números das salas quem contém pessoas.
Cada uma das M linhas seguintes descreve um escorregador, e contém
três inteiros A, B e D, indicando que existe um escorregador da sala A (mais alta) para a sala B (mais baixa), de comprimento D metros.
Saída
Seu programa deve produzir uma única linha, contendo um único número inteiro,
o menor tempo possível, em segundos, para prevenir o acidente, ou -1 caso isso não seja possível.
Restrições
- Sempre há pessoas nas salas 1 e N
- 2 ≤ N ≤ 105
- 0 ≤ M ≤ 3 x 105
- 2 ≤ C ≤ 100
- 1 ≤ D ≤ 104
- 0 ≤ K ≤ 109
Informações sobre a pontuação
- Em um conjunto de casos de testes somando 30 pontos, C = 2.
Exemplos
Entrada
5 7 4 7
1 2 3 5
1 2 6
1 3 9
2 3 5
2 5 16
3 5 14
3 4 6
4 5 11
|
Saída
7
|
Entrada
4 4 3 3
1 3 4
1 2 1
1 2 3
3 2 3
3 4 3
|
Saída
-1
|
Entrada
4 3 2 5
4 1
1 2 1
4 3 3
2 4 3
|
Saída
0
|
