2768 - Grafo do Dabriel

• ID: 2768
• IdBecrowd: 2768
• Tags: grafos, strings
• Nível: 7
• Tempo Limite: 1 segundos
• Memória: 200 MB
• Categoria: Grafos
• Autor: Gabriel Duarte, UFF

Descrição

Dabriel acaba de receber um grafo de presente e deseja realizar algumas operações sobre ele, porém como está muito ocupado decidiu pedir sua ajuda. Você deverá responder diversas consultas do tipo U , V , K , onde vc deverá imprimir o menor caminho de U até V , caso exista, onde os vértices visitados, excluindo U e V , devem ser menores ou iguais a K .

Entrada

A entrada é composta por diversos casos de teste. A primeira linha terá 2 inteiros N , M (1 ≤ N ≤ 100, 1 ≤ M ≤ N ( N -1)/2). Nas próximas M linhas terá 3 inteiros U , V , W (1 ≤ U , V ≤ N , 0 ≤ W ≤ 210³), indicando que o vértice U tem uma ligação bidirecional com o vértice V com um custo de W . Na próxima linha terá 1 inteiro Q (1 ≤ Q ≤ 10⁵). Nas próximas Q linhas terá uma consulta U , V , K (1 ≤ U , V , K ≤ N ).

Saída

Para cada consulta você deverá imprimir o menor custo seguindo as restrições do texto. Caso não exista resposta imprima -1.

Exemplos

Exemplo de Entrada

5 6

                                1 2 1

                                2 3 3

                                1 4 1

                                4 3 2

                                3 5 1

                                1 5 50

                                6

                                1 5 1

                                1 5 2

                                1 5 3 

                                1 5 4

                                1 5 5

                                1 3 1

Exemplo de Saída

50

                                50

                                5

                                4

                                4

                                -1