Viagem

Você está viajando pelo arquipélago de Kiri, que é composto por um grande número de ilhas. Não há pontes entre as ilhas, de modo que a única maneira de viajar entre as ilhas é por navio.

Há várias rotas de navios disponíveis. Cada rota conecta duas ilhas distintas $A$ e $B$ e pode ser usada nas duas direções (de $A$ para $B$ ou de $B$ para $A$). Cada rota tem um certo tempo de percurso (o mesmo nas duas direções) e um custo (o mesmo nas duas direções).

No momento você quer ir da ilha $X$ para outra ilha $Y$, mas quer gastar no máximo um certo valor com a viagem. Você também está com pressa e gostaria de chegar o mais rapidamente possível ao seu destino.

Dados a lista das rotas disponíveis, com seus custos e tempos de percurso, escreva um programa para determinar se é possível chegar ao destino gastando no máximo o valor previsto para a viagem, e nesse caso qual o menor tempo para chegar ao destino. Note que pode não ser possível chegar ao destino, seja porque não há rota disponível ou porque o valor alocado para a viagem não é suficiente.

Por exemplo, considere o caso mostrado na figura abaixo, em que você está na ilha 1 e quer ir para a ilha 4:

1. Se o valor previsto é 10, a resposta é 5 e o caminho ótimo é $1 \rightarrow 2 \rightarrow 4$. Note que este caminho custa $4 + 6 = 10$ e demora tempo $4 + 1 = 5$.
2. Se o valor previsto é 7, a resposta é 7 e o caminho ótimo é $1 \rightarrow 2 \rightarrow 3 \rightarrow 4$, que custa $4 + 2 + 1 = 7$ e demora tempo $4 + 2 + 1 = 7$.
3. Se o valor previsto é 3, a resposta é 8 e o caminho ótimo é $1 -> 3 -> 4$, usando a aresta entre 1 e 3 que demora tempo 7 e tem custo 2. Note que este caminho custa $2 + 1 = 3$ e demora tempo $7 + 1 = 8$.
4. Se o valor previsto é 2, a resposta é 9 e o caminho ótimo é $1 -> 3 -> 4$, usando a aresta entre 1 e 3 que demora tempo 8 e tem custo 1, note que este caminho custa $1 + 1 = 2$ e demora tempo $8 + 1 = 9$.
5. Se o valor previsto é 1, não existe caminho que satisfaça as restrições, por isso a resposta é $-1$.

Entrada

A primeira linha da entrada contém três inteiros $V$, $N$ e $M$, respectivamente o valor disponível para a viagem, o número de ilhas e o número de rotas. As ilhas são identificadas por inteiros de 1 a $N$. Cada uma das $M$ linhas seguintes descreve uma rota e contém quatro inteiros $A_i$, $B_i$, $T_i$ e $P_i$, onde $A_i$ e $B_i$ representam ilhas, $T_i$ o tempo de percurso e $P_i$ o custo de uma passagem para essa rota. A última linha da entrada contém dois inteiros $X$ e $Y$, o início e o destino da sua viagem.

Saída

Seu programa deve produzir uma única linha na saída, que deve conter um único inteiro, o menor tempo necessário para chegar ao destino, ou o valor $-1$ caso não seja possível chegar ao destino.

Restrições

• $2 \leq N \leq 10\ 000$
• $1 \leq M \leq 2\ 000$
• $1 \leq V \leq 200$
• $1 \leq A_i, B_i \leq N$, $A_i \neq B_i$, para $1 \leq i \leq M$.
• Pode haver mais de uma rota entre o mesmo par de ilhas.
• $1 \leq T_i \leq 100\ 000$, para $1 \leq i \leq M$.
• $0 \leq P_i \leq 200$, para $1 \leq i \leq M$.
• $1 \leq X,Y \leq N$

Informações sobre a pontuação

• Para um conjunto de casos de testes valendo $20$ pontos, $N \leq 200$ e $P_i = 0$ para $1 \leq i \leq M$.
• Para um conjunto de casos de testes valendo outros $10$ pontos, $N \leq 10\ 000$ e $P_i = 0$ para $1 \leq i \leq M$.
• Para um conjunto de casos de testes valendo outros $30$ pontos, $N \leq 100$ e $V \leq 10$.
• Para um conjunto de casos de testes valendo outros $40$ pontos, nenhuma restrição adicional.

Exemplo de entrada 1

10 4 7
1 2 4 4
1 3 7 2
3 1 8 1
3 2 2 2
4 2 1 6
3 4 1 1
1 4 6 12
1 4

Exemplo de saída 1

5

Exemplo de entrada 2

3 3 3
1 2 5 2
3 2 8 2
1 3 1 4
1 3

Exemplo de saída 2

-1