XXVI Olimpíada Brasileira de Informática
Submeta sua solução

Nome do arquivo: usina.x, onde x deve ser c, cpp, java, js ou py

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
	
Promoção
logo sbc
Patrocínio
Apoio
Coordenação