Convex Hull

Matheus está viajando com o seu navio em um arquipélago. Seu navio tem um casco convexo que tem $k$ centímetros de espessura. O aruipélago tem $n$ ilhas, numeradas de $1$ a $n$ . Existem $m$ rotas marítmas entre as ilhas, onde a $i$ -ésima rota liga duas diferentes ilhas $a_i\ b_i$ , demora $t_i$ minutos e diminui a espessura do casco do navio em $h_i$ centímetros. Podem haver varias rotas entre o mesmo par de ilhas.

Matheus quer viajar entre as ilhas $A$ e $B$ , por meio de uma sequência de rotas marítmas, de forma que o casco do seu navio continue intacto. Em outras palavras, de tal forma que a soma do $h_i$ das rotas seja entritamente menor que $k$ .

Além disso Matheus está apressado, e quer minímizar o tempo necessário para chegar na ilha $B$ saindo da ilha $A$ . Pode não ser possível chegar na ilha $B$ partindo da ilha, seja por não haver rotas suficientes ou por o casco do navio ser destruído.

Entrada

A primeira linha contém 3 inteiros $k, n, m\ (1 \leq k \leq 200, 2 \leq n \leq 2000, 1 \leq m \leq 10000)$ , separados por espaços.

As próxmias $m$ linhas contém 4 inteiros, $a_i\ b_i\ t_i\ h_i\ (1 \leq a_i,b_i \leq n, 1 \leq t_i \leq 10^5, 0 \leq h_i \leq 200)$ . A $i$ -ésima linha descreve a $i$ -ésima rota, (que vai da ilha $a_i$ , para a ilha $b_i$ , leva $t_i$ minutos e diminui o casco em $h_i$ centímetros). Perceba que $a_i \neq b_i$ .