Visita entre cidades

A Linearlândia é composta de N cidades, numeradas de 1 até N. Para alguns pares de cidades existe exatamente uma estrada bidirecional entre as duas cidades do par. Os pares de cidades ligados diretamente por uma estrada são escolhidos de forma que sempre é possível ir de qualquer cidade para qualquer outra cidade por um, e somente um, caminho (um caminho é uma sequência de estradas, sem repetição).

Dada a lista de pares de cidades ligados diretamente por estradas, as distâncias entre os pares de cidades, uma cidade origem e uma cidade destino, seu programa deve computar qual a distância entre a cidade de origem e a cidade destino, usando as estradas. Por exemplo, na figura, a distância para ir da cidade 12 para a cidade 7 é 23; a distância da cidade 15 para a cidade 12 é 16; e a distância da cidade 7 para a cidade 15 é 33.

Entrada

Saída

Restrições

• 2 ≤ N ≤ 10000
• 1 ≤ A ≤ N, 1 ≤ B ≤ N, A ≠ B
• 1 ≤ P ≤ N, 1 ≤ Q ≤ N
• 1 ≤ D ≤ 100

Exemplos

4 2 4
1 2 10
2 3 11
3 4 12

23
	

16 15 7
3 5 8
12 3 3
5 1 5
2 1 5
4 1 10
6 1 3
7 1 7
12 8 3
12 9 3
12 10 3
12 11 3
3 13 6
13 14 6
15 13 7
15 16 10

33