该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

夜色铺满了立交桥，下课后的徐老师正在物流公司打工，他时刻盯着城市物流网络的调度屏。 这座城市有若干物流站点与配送道路，每条道路都像是只在特定时刻敞开的闸门：只有在开放区间里出发，货车才可以驶上去；一旦驶上了路，就算关闭时刻到了，也允许把这条路走完。

公司给了徐老师一点“特权”：至多对 k 条道路做一次时间端点的微调（把该路的开放起始时间或结束时间中的一个改到任何你想要的时刻）。除此之外，货车也可以在站点等待，等路开了再走。

现在，货车从 1 号站点在时刻 0 出发，目标是到达 n 号站点。请你帮助徐老师计算：完成这趟配送，最少需要多少小时？

题面描述

• 有 n 个站点，m 条无向或有向道路（若未声明，按无向或按输入含两端点理解即可，以输入为准）。

• 第 i 条道路给出五元组

  $x_i, y_i, s_i, t_i, w_i$

  含义为：连接站点 $x_i$ 与 $y_i$ 的道路在时间区间 $$$s_i,,t_i$$$ 允许开始上路；一旦在该区间内开始行驶，行驶时长为 $w_i$，可在关闭后继续行驶直至走完。 若在某站点的到达时刻早于道路开放，可以选择等待至开放再出发。

• 可调整能力：你可以选择至多 k 条不同的道路，并对每条被选中的道路仅调整一个端点：要么把 its $s_i$（开放起始）改到任意值，要么把 its $t_i$（结束）改到任意值。

  • 调整一次只作用于一条道路的一个端点；同一条道路不能再被第二次调整（即不允许同时改它的 $s_i$ 和 $t_i$）。
  • “改到任意值”意味着可以把 $s_i$ 提前/推后，或把 $t_i$ 提前/推后（通常会把 $s_i$ 调到更早、或把 $t_i$ 调到更晚，以放宽限制）。

• 出发时刻固定为 0。需要输出从 1 号到 n 号的最短到达时间；若无法到达，输出 -1。

输入格式

• 多组数据。第一行给出整数 $T$。

• 对于每组数据：

  • 第一行：三个整数 $n, m, k$。
  • 接下来 $m$ 行：每行五个整数$$x_i; y_i; s_i; t_i; w_i$$ 分别表示道路两端点、开放起始时间、关闭时间与道路长度（行驶时长）。

约定：时间单位为“小时”；起点到达时间为 0。若在某条路的开始时刻 $\tau$ 满足 $\tau \in$$s_i, t_i$$$，则可上路并在 $\tau + w_i$ 抵达终点；即使 $\tau + w_i > t_i$ 也被允许（只要上路时刻在区间内）。

输出格式

• 对每组数据，输出一行：从 1 号站到 n 号站的最短用时；若无解输出 -1。

输入输出样例

2
5 5 1
1 2 1 2 2
2 3 2 4 3
3 5 1 10 1
4 5 2 4 3
1 4 2 4 2
5 5 0
1 2 1 2 2
2 3 2 4 3
3 5 1 10 1
4 5 2 4 3
1 4 2 4 2

5
7

数据范围

• 对于 $20$ 的数据：$2 \le n \le 10$, $0 \le m \le 30$, $0 \le k \le 0$, $1 \le T \le 2$。
• 对于 $50$ 的数据：$2 \le n \le 1002$, $0 \le m \le 2000$, $0 \le k \le 30$。
• 对于 $100$ 的数据： $ 2 \le n \le 30002,\quad 0 \le m \le 60000,\quad 0 \le k \le 30,\quad 0 \le s_i,t_i,w_i \le 10^{9},\quad 1 \le T \le 5 $