题目描述

$n$ 个点 $m$ 条边的有权无向图，每条边有一个开放时间 $[s,t]$，只有在开放时间内，你才可以走上这条路，并在路径长度个单位时间抵达终点。（若截止时间之前仍在路径上，可以走完这条路经到达终点。）

可以进行 $k$ 次修改一个边的一个时间，问最快从 $1$ 到达 $n$ 时间。(出发的时间是 $0$，如果到达某个点时还没到某条边的开放时间，除了直接修改开放时间之外，你也可以在这个点原地休息，直到开放时间再出发。)

输入格式

本题有 $T$ 组测试数据。

对于每一组测试数据，第一行三个数 $n,m,k$。

接下来 $m$ 行，每行五个整数 $x_{i},y_{i},s_{i},t_{i},w_{i}$ 表示第 $i$ 条边的两个端点,开放时间,关闭时间,路径长度。

输出格式

对于每组数据，输出一行答案,保证最终可以到点 $n$。

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

样例解释

样例的图如上（注意本题为无向图，箭头只是为了指示下面样例解释中的两条路径）

可以把 $1$ 到 $4$ 这条有向边的开放时间的起始时间改为 $0$，即可通过 $1,4,5$ 这条路径，这样修改一次，花费 $5$ 的时间可以到达终点。

如果不允许修改。可以在起点等待到时间 $2$ 再出发，沿着 $1,4,5$ 到达终点；也可以在起点等待到时间 $1$ 再出发，沿着 $1,2,3,5$ 到达终点。两种方案到达终点的时间都是 $7$。

数据规模与约定

对于 $20\%$ 的数据，$2 \le n \le 12$，$0 \le m \le 30$，$0 \le k \le 1$，$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$，$0 \le m \le 60000$，$0 \le k \le 30$，$0 \le s,t,w \le 10^9$，$1\le T\le 5$