Problem Description

Given an undirected graph with $n$ points and $m$ edges, each edge has two weights $t_{i}$ and $h_{i}$.

You need to find a path from $s$ to $t$ such that the sum of $h_{i}$ on the path is $< k$, and the sum of $t_{i}$ is as small as possible. You only need to output this minimum value. If no path satisfying the condition can be found, output $-1$.

Input Format

The first line contains three integers $k, n, m$.

The next $m$ lines each contain four integers $u_{i}, v_{i}, t_{i}, h_{i}$, representing an edge between $u_{i}$ and $v_{i}$, with edge weights $\{t_{i}, h_{i}\}$.

The last line contains two integers $s, t$.

Output Format

If there exists a path satisfying the condition, output one line with one integer, the minimum possible sum of $t_{i}$.

Otherwise, output one line with $-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

7

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

-1

Hint

Constraints:

For $20\%$ of the testdata, $k = 1$, $2 \leq n \leq 200$.

For another $20\%$ of the testdata, $k = 1$, $2 \leq n \leq 2 \times 10^{3}$.

For $100\%$ of the testdata, $0 \leq h_{i} \leq 200$, $1 \leq t_{i} \leq 10^{5}$, $1 \leq k \leq 200$, $2 \leq n \leq 2 \times 10^{3}$, $1 \leq m \leq 10^{4}$, and $s \neq t$.

Translated by ChatGPT 5