# 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
 ≤ 2*10³), 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
```