Ilhas

Os moradores das Ilhas Brasileiras Ocidentais (IBO) são assíduos jogadores do mais recente jogo online, Magos e Guerreiros. Tão competitivas se tornaram as partidas de Magos e Guerreiros na IBO, que a empresa criadora do jogo decidiu instalar em uma das ilhas um servidor dedicado apenas aos jogadores da IBO.

Entretanto, a empresa sabe que, se os jogadores acharem que o novo servidor é injusto, eles irão parar de jogar Magos e Guerreiros, gerando incontáveis perdas. Para avaliar se o novo servidor é justo, os jogadores vão comparar o desempenho do jogo na ilha que tem a conexão mais rápida e o desempenho na ilha que tem a conexão mais lenta com o novo servidor. Se a diferença de desempenho for muito grande, os residentes da ilha mais distante se sentirão injustiçados e abandonarão o jogo.

A conexão de internet da IBO funciona através de um sistema de cabos de fibra ótica. Pares de ilhas são conectados por cabos, e cada cabo toma um certo tempo (chamado de ping) para comunicar informação entre as duas partes. Quando duas ilhas se comunicam através de uma série de cabos (portanto, através de ilhas intermediárias), o ping entre elas é a soma dos pings de cada cabo no caminho. A rede da IBO foi implementada por ótimos programadores e, portanto, um par de ilhas sempre se comunica através do caminho com menor ping possível.

Dada a configuração da rede da IBO e a ilha em que a empresa deseja instalar o novo servidor, determine a diferença entre os pings da ilha com menor e maior pings até o servidor.

Entrada

A primeira linha contém N e M, o número de ilhas e o número de cabos de fibra ótica, respectivamente. As ilhas são numeradas de 1 a N. Cada uma das M linhas seguintes contém três inteiros U_i, V_i e P_i e descreve um cabo entre as ilhas U_i e V_i com ping P_i (note que cabos transmitem informação em ambas as direções). Finalmente, a última linha contém um inteiro S, o número da ilha em que o servidor será instalado.

Cada par de ilhas é conectado por no máximo um cabo de fibra ótica, e nenhum cabo conecta uma ilha a si mesma. É garantido que qualquer ilha consegue se comunicar com qualquer outra através de algum caminho de cabos de fibra ótica.

Saída

Seu programa deve produzir uma única linha, contento um inteiro,a diferença entre o ping da ilha com maior ping até o servidor, e o da ilha com menor ping até o servidor. Note que a ilha em que o servidor se encontra não é considerada no cálculo do menor ping.

Restrições

• 2 ≤ N ≤ 1000
• N-1 ≤ M ≤ 10⁵
• 1 ≤ U_i ≤ N
• 1 ≤ V_i ≤ N
• 1 ≤ S ≤ N
• 1 ≤ P_i ≤ 1000

Informações sobre a pontuação

• Para um conjunto de casos de testes valendo 30 pontos, 2 ≤ N ≤ 100 e N-1 ≤ M ≤ 1000.

Exemplos

4 5
2 1 5
1 3 4
2 3 6
4 2 8
3 4 12
1

9
	

6 11
1 2 3
6 1 9
2 6 10
2 3 8
5 3 3
4 3 2
2 4 12
6 4 1
4 5 9
1 5 16
5 6 5
5

11