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

Saída

Restrições

• Sempre há pessoas nas salas 1 e N
• 2 ≤ N ≤ 10⁵
• 0 ≤ M ≤ 3 x 10⁵
• 2 ≤ C ≤ 100
• 1 ≤ D ≤ 10⁴
• 0 ≤ K ≤ 10⁹

Informações sobre a pontuação

• Em um conjunto de casos de testes somando 30 pontos, C = 2.

Exemplos

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

7
	

4 4 3 3
1 3 4
1 2 1
1 2 3
3 2 3
3 4 3

-1
	

4 3 2 5
4 1
1 2 1
4 3 3
2 4 3

0