问题 A: 高速

问题 A: 高速

时间限制: 1 Sec  内存限制: 128 MB
提交: 15  解决: 4
[提交][状态][讨论版][命题人:]

题目描述

教练开车去东北,因为比赛地点在东北。共有 n 座城,已知教练在 s 城,比赛地点在 t 城,n 座城之间共有 m 条高速,每条高速连接两座城市,每两座城市之间最多两条高速。每条高速都有权值 v,表示两个城市之间最快可以 v 小时到达。

然而高速不是永久开放的,每条高速都会有一段开放时间 [ a,b ],表示该高速在 a ~ b 小时范围之间开放,其余时间处于关闭状态,不能通过任何车辆。例如 [ 24,27 ]表示该路在第 24 小时到 27 小时之间开放。

已知教练在 0 时刻出发,他最快多少小时可以到达 t 城。

(PS:由于刹车坏掉了,因此车一旦启动就不能停下来,也就是说车不能停于某点或某边,不过车可以来回无限次在两地之间穿梭)

输入

多组测试样例,首行输入 t,表示 t 组样例。

图为无向图,s 城固定为 1 点,t 城固定为 n 点。

每组样例第 1 行,输入n,m(1 < n ≤ 100,0 < m ≤ 1000)。

接下来 m 行,每行 5 个数值x,y,v,l,f。表示 x 与 y 有一条高速,耗时为 v。该路开放时间为[ l,f ]。

数据保证教练可以到达终点,只不过是时间问题。

输出

输出一个数值,即最少耗时。

样例输入

1
5 4
2 3 1 5 11
2 5 1 3 18
4 3 1 7 14
1 4 1 0 15

样例输出

10
[提交][状态]