本题需要文件读写

文件 IO 为：输入文件 route.in，输出文件 route.out。请使用上述文件名读入和输出。

题目描述

一片海域中有 $N$ 座岛屿，编号为 $1$ 到 $N$，岛屿之间有 $M$ 条航线。每条航线连接两座不同的岛屿，两个方向都可以通行。同一对岛屿之间可能有多条航线。

经过一条航线需要一定的航行时间。航线中的礁石还会使船体损耗一定的厚度；即使两条航线连接相同的岛屿，它们的航行时间和船体损耗也可能不同。

一艘船的初始船体厚度为 $K$。船要从岛屿 $A$ 出发，到达另一座岛屿 $B$。途中不能修复船体，因此经过各条航线造成的损耗需要累加。船体剩余厚度必须始终大于 $0$，也就是说，航行过程中的累计损耗必须严格小于 $K$。损耗为 $0$ 的航线也可以通行。

请你计算，在满足船体厚度要求的前提下，从 $A$ 到达 $B$ 最少需要多少时间。如果无法到达，则输出 -1。

一个输入文件中包含多组相互独立的航行任务。每组任务都会重新给出海域、船体厚度和起终点，各组之间没有任何继承关系。

输入格式

第一行包含一个整数 $T$，表示航行任务的组数。

接下来依次给出 $T$ 组数据。每组数据的格式如下：

• 第一行包含三个整数 $K, N, M$，分别表示初始船体厚度、岛屿数量和航线数量。
• 接下来 $M$ 行，每行包含四个整数 $u, v, t, h$，表示岛屿 $u$ 与岛屿 $v$ 之间有一条双向航线；每次经过它需要 $t$ 单位时间，并使船体损耗 $h$ 单位厚度。
• 最后一行包含两个整数 $A, B$，分别表示出发岛屿和目的岛屿。

两组数据之间不需要空行。

输出格式

输出 $T$ 行，每行一个整数。第 $c$ 行表示第 $c$ 组任务的最短航行时间；如果这一组任务无法完成，则在该行输出 -1。不需要输出任务编号。

样例输入 1

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

样例输出 1

7

说明

样例解释

可以按 $1 \to 2 \to 3 \to 4$ 的顺序航行，总时间为 $4+2+1=7$，累计损耗为 $4+2+1=7$，严格小于船体厚度 $10$。

路线 $1 \to 2 \to 4$ 只需要 $5$ 单位时间，但累计损耗恰好为 $10$，不能使用；直接从 $1$ 到 $4$ 需要 $6$ 单位时间，但损耗为 $12$，也不能使用。不存在满足要求且用时小于 $7$ 的路线，因此答案为 $7$。

其它样例说明

• 样例 2：见选手目录下的 route/route2.in 与 route/route2.ans。该样例满足测试点 $1 \sim 4$ 的约束。
• 样例 3：见选手目录下的 route/route3.in 与 route/route3.ans。该样例满足测试点 $5 \sim 8$ 的约束。
• 样例 4：见选手目录下的 route/route4.in 与 route/route4.ans。该样例满足测试点 $9 \sim 20$ 的约束。
• 样例 5：见选手目录下的 route/route5.in 与 route/route5.ans。该样例满足测试点 $9 \sim 20$ 的约束。
• 样例 6：见选手目录下的 route/route6.in 与 route/route6.ans。该样例满足测试点 $9 \sim 20$ 的约束。

数据范围

对于所有输入数据，保证：

• $1 \le T \le 10$。
• 每组满足 $1 \le K \le 200$，$2 \le N \le 2000$，$1 \le M \le 10000$。
• 每条航线满足 $1 \le u, v \le N$ 且 $u \ne v$，$1 \le t \le 10^5$，$0 \le h \le 200$。
• 每组满足 $1 \le A, B \le N$ 且 $A \ne B$。
• 同一输入文件内，各组的 $N$ 之和不超过 $4000$，各组的 $M$ 之和不超过 $20000$。
• 所有输入均为整数，航线允许重复。

各测试点的附加限制如下表所示：

点击下载大样例