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 \leq N \leq 10000$;
• $1 \leq A \leq N$, $1 \leq B \leq N$, $A \neq B$;
• $1 \leq P \leq N$, $1 \leq Q \leq N$;
• $1 \leq D \leq 100$.

Exemplos:

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

23

Para submeter sua solução, use esse link.