Barcos da Nlogônia

Como todos sabem, a Nlogônia é um arquipélago que mantém a tradição milenar de não permitir a construção de pontes. Assim, o transporte público entre as ilhas se dá por meio de barcos.

Para cada par de ilhas há no máximo um barco que faz o transporte de ida e volta entre as duas ilhas; ou seja, pode não haver transporte direto entre um determinado par de ilhas. No entanto, é possível ir de qualquer ilha para qualquer outra ilha utilizando apenas os barcos de transporte público (note que pode ser preciso passar por outras ilhas no trajeto).

Os barcos de transporte público da Nlogônia não são todos iguais: cada barco tem um limite máximo de passageiros que ele pode carregar.

Cada ilha tem um time de basquete, com um grupo de fãs. Todos os fãs de um time são moradores da mesma ilha do time para o qual torcem. Nos dias de jogo, o grupo de fãs do time visitante sempre planeja viajar usando apenas barcos de transporte público, todos juntos, para a ilha onde acontecerá o jogo (ou seja, todos os membros do grupo juntos, durante todo o trajeto). Mas os fãs sabem que isso talvez não seja possível devido ao limite de passageiros dos barcos de transporte público. Você poderia ajudá-los?

Dados a lista dos barcos existentes, com os respectivos limites de passageiros, e uma série de consultas, cada uma com a ilha de início do trajeto e a ilha onde ocorrerá o jogo, sua tarefa é determinar, para cada consulta da entrada, qual o maior número de torcedores que o grupo pode ter para poder viajar junto.

Entrada

A primeira linha contém dois inteiros $N$ e $B$, indicando, respectivamente, o número de ilhas da Nlogônia e o número de barcos de transporte público que ligam as ilhas. As ilhas nlogonianas são identificadas por números de $1$ a $N$.

Cada uma das $B$ linhas seguintes descreve o trajeto de um barco de transporte público e contém três inteiros $I$, $J$ e $P$, onde $I$ e $J$ indicam as duas ilhas ligadas por esse barco e $P$ indica o limite de passageiros do barco. Note que o barco pode fazer o transporte tanto de $I$ para $J$ quanto de $J$ para $I$.

A linha seguinte contém um inteiro $C$ que indica o número de consultas. Finalmente, cada uma das $C$ linhas seguintes descreve uma consulta e contém dois inteiros $X$ e $Y$ indicando, respectivamente, a ilha de início e a ilha do local do jogo.

Saída

Para cada consulta, na ordem em que elas foram descritas na entrada, seu programa deve produzir uma linha contendo um único inteiro, o maior número de passageiros que o grupo pode ter para viajar junto do início até o local do jogo.

Restrições

• $2 \leq N \leq 10^5$
• $1 \leq B \leq 10^5$
• $1 \leq I \leq N$, $1 \leq J \leq N$ e $I \neq J$, cada par $I, J$ aparece no máximo uma vez na entrada.
• $1 \leq P \leq 10^5$
• $1 \leq C \leq 5\times10^4$
• $1 \leq X \leq N$, $1 \leq J \leq N$ e $X \neq Y$

Informações sobre a pontuação

A tarefa vale $100$ pontos. Estes pontos estão distribuídos em subtarefas, cada uma com suas restrições adicionais às definidas acima:

• Subtarefa 1 (11 pontos): $N = 3$
• Subtarefa 2 (13 pontos):
  • $N \leq 1\ 000$
  • $B = N - 1$
  • Para todo $1 \leq I \leq N - 1$, há um barco de transporte público entre as ilhas $I$ e $I + 1$.
  • $C\leq 1\ 000$
• Subtarefa 3 (22 pontos): $B = N - 1$
• Subtarefa 4 (33 pontos):
  • $N \leq 1\ 000$
  • $C = 1$
• Subtarefa 5 (21 pontos): Nenhuma restrição adicional.

Seu programa pode resolver corretamente todas ou algumas das subtarefas (elas não precisam ser resolvidas em ordem). Sua pontuação final na tarefa é a soma dos pontos de todas as subtarefas resolvidas corretamente por alguma das suas submissões.

Exemplos

Exemplo de entrada 1

5 6
1 4 50
1 5 85
2 3 60
2 4 80
4 5 75
1 3 40
2
2 1
1 3

Exemplo de saída 1

75
60

Explicação do exemplo 1: A seguir temos uma visualização das ilhas e dos barcos que conectam essas ilhas:

Perceba que é possível 75 pessoas irem da ilha 2 à ilha 1 usando os seguintes barcos: - da ilha 2 para a ilha 4, onde o barco suporta até 80 passageiros. - da ilha 4 para a ilha 5, onde o barco suporta até 75 passageiros. - da ilha 5 para a ilha 1, onde o barco suporta até 85 passageiros.

Perceba também que é possível 60 pessoas irem da ilha 1 à ilha 3 usando os seguintes barcos: - da ilha 1 para a ilha 5, onde o barco suporta até 85 passageiros. - da ilha 5 para a ilha 4, onde o barco suporta até 75 passageiros. - da ilha 4 para a ilha 2, onde o barco suporta até 80 passageiros. - da ilha 2 para a ilha 3, onde o barco suporta até 60 passageiros.

Exemplo de entrada 2

7 6
1 2 30
2 3 20
3 4 10
4 5 50
5 6 40
6 7 100
4
2 7
4 7
1 3
6 7

Exemplo de saída 2

10
40
20
100

Explicação do exemplo 2: A seguir temos uma visualização das ilhas e dos barcos que conectam essas ilhas: