龙傲天的逃离
该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
Description
龙傲天成功干掉了 BOSS,而 BOSS 的巢穴也将要坍塌。
BOSS 的巢穴由 个洞窟组成,洞窟之间由栈道连接,可以相互到达,总共有 条栈道,栈道的长度不尽相同。
由于 BOSS 已经被打败,栈道也很难维持下去了,每个栈道都会在一定时间后毁坏。
现在龙傲天想知道,自己最快能在什么时候到达巢穴的出口?
Input Format
第一行一个整数 ,代表数据的组数。
接下来 组数据,每组数据的第一行包含两个整数 ,分别代表洞窟的数量和栈道的数量。
接下来 行,每行四个整数 $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)$,代表洞窟 和洞窟 有一条耗时为 秒的栈道,并且这个栈道会在 秒后毁坏。
龙傲天的初始位置总为洞窟 ,巢穴的出口总为洞窟 。
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