13613번 - Dona Minhoca 다국어

Dona Minhoca fica furiosa quando ouve as pessoas dizerem que minhocas são bichos palíndromes, nos quais não é possível distinguir a cabeça do rabo. Que infâmia!

Dona Minhoca vive em uma linda caverna, composta de salões e túneis. Cada túnel liga dois salões distintos e pode ser usado nas duas direções. Um “ciclo” na caverna é uma sequência de salões s₁, s₂, . . . , s_n, s_n+1 = s₁ , tais que s_i ≠ s_i+1 e (s_i, s_i+1) é um túnel, para 1 ≤ i ≤ n. A caverna de Dona Minhoca pode conter ciclos, mas cada salão faz parte de no máximo um ciclo da caverna. Os túneis e salões são estreitos, de forma que se uma parte do corpo de Dona Minhoca ocupa um túnel ou salão, não há espaço para Dona Minhoca entrar novamente por esse túnel ou salão.

Alguns salões da caverna têm acesso a partir da superfície. Dona Minhoca tem um mapa que descreve a caverna, informando para cada túnel o seu comprimento e quais dois salões o túnel liga. Dona Minhoca também é vaidosa e conhece o seu próprio comprimento.

Dona Minhoca quer saber, para os salões que têm acesso à superfície, se é possível entrar na caverna pelo salão, percorrer a menor distância possível dentro da caverna, e sair novamente pelo mesmo salão que entrou, sempre andando para a frente, sem nunca dar marcha-a-ré. Você pode ajudá-la?

A primeira linha contém dois inteiros S (2 ≤ S ≤ 10⁴ ) e T (1 ≤ T ≤ 2S) representando respectivamente o número de salões e o número de túneis da caverna. Os salões são identificados por inteiros de 1 a S. Cada uma das T linhas seguintes descreve um túnel e contém três inteiros A, B e C (1 ≤ A < B ≤ S; 1 ≤ C ≤ 100), onde A e B representam os salões ligados pelo túnel, e C representa o comprimento do túnel. Um salão é ligado por túneis a no máximo outros 100 salões e cada dois salões são ligados por no máximo um túnel. A próxima linha contém um inteiro Q (1 ≤ Q ≤ 100), que indica o número de consultas. Cada uma das Q linhas seguintes descreve uma consulta, e contém dois inteiros X (1 ≤ X ≤ S) e M (1 ≤ M ≤ 10⁵ ), que indicam respectivamente o salão pelo qual Dona Minhoca quer entrar e o comprimento de Dona Minhoca.

Para cada consulta da entrada seu programa deve produzir apenas uma linha, contendo apenas um número inteiro, o comprimento do percurso mínimo que Dona Minhoca deve percorrer dentro da caverna para entrar e sair pelo salão indicado na consulta, sem dar marcha-a-ré. Se não for possível para Dona Minhoca entrar e sair sem dar marcha-a-ré, a linha deve conter o valor −1.