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
A primeira linha da entrada contém três inteiros N, A e B, representando o número de cidades na Linearlândia, a cidade origem e a cidade destino, respectivamente. As cidades são identificadas por inteiros de 1 a N. As N-1 linhas seguintes contém, cada uma, três inteiros P, Q e D, indicando que existe uma estrada ligando diretamente as cidades P e Q, com distância D.Saída
Seu programa deve imprimir uma linha contendo um inteiro representando a distância para ir de A até B pelas estradas de Linearlândia.Restrições
- 2 ≤ N ≤ 10000
- 1 ≤ A ≤ N, 1 ≤ B ≤ N, A ≠ B
- 1 ≤ P ≤ N, 1 ≤ Q ≤ N
- 1 ≤ D ≤ 100
Exemplos
Entrada
4 2 4 1 2 10 2 3 11 3 4 12 |
Saída
23 |
Entrada
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 |
Saída
33 |
