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

Description

龙傲天成功干掉了 BOSS，而 BOSS 的巢穴也将要坍塌。

BOSS 的巢穴由 $n$ 个洞窟组成，洞窟之间由栈道连接，可以相互到达，总共有 $m$ 条栈道，栈道的长度不尽相同。

由于 BOSS 已经被打败，栈道也很难维持下去了，每个栈道都会在一定时间后毁坏。

现在龙傲天想知道，自己最快能在什么时候到达巢穴的出口？

Input Format

第一行一个整数 $T(1 \le T \le 10)$ ，代表数据的组数。

接下来 组数据，每组数据的第一行包含两个整数 $n,m(2 \le n \le 100, 1 \le m \le 10^5)$，分别代表洞窟的数量和栈道的数量。

接下来 $m$ 行，每行四个整数 $u,v,w,t(1 \le u,v \le n, u\ne v, 1 \le w \le 10^4, 1 \le t \le 10^6)$，代表洞窟 $u$ 和洞窟 $v$ 有一条耗时为 $w$ 秒的栈道，并且这个栈道会在 $t$ 秒后毁坏。

龙傲天的初始位置总为洞窟 $1$，巢穴的出口总为洞窟 $n$ 。

Output Format

对于一组数据，输出一个整数，代表龙傲天最快可以在多少秒到达巢穴的出口。

如果龙傲天不能到达巢穴的出口，输出-1。

3
5 6
5 3 6 16
3 1 9 15
4 2 6 2
3 2 10 11
1 5 5 14
3 4 2 13
5 5
5 4 6 1
5 3 7 17
4 2 7 14
2 1 5 4
2 4 1 15
2 1
1 2 3 3​

5
-1
3