#524. 「多校联考 Round 3」卡车

内存限制:512 MiB 时间限制:1000 ms 输入文件:truck.in 输出文件:truck.out
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

小 Y 是一个喜欢玩游戏的 OIer,在她玩过的游戏当中,最刺激的当属《欧洲卡车模拟》了。在这款游戏中,小 Y 的任务是驾驶自己的货车,在欧洲平原上,根据每条订单的要求,从起点运送货物到达终点。由于欧洲的各个国家的发展情况不同,道路的崎岖状况也有所不同。

像很多游戏一样,《欧洲卡车模拟》具有简单的养成系统,人物驾驶卡车的熟练度会随时间的流逝而上升,具体表现为能够在更少的时间内通过一条道路。

方便起见,我们作出如下的约定:

  • 欧洲可以抽象为一张 个点, 条边的无向图,通过每条道路所需的时间为

  • 每条道路都具有一个崎岖度 的大小将会改变通过改条道路的时间。具体地,若小 Y 在第 秒经过第 条道路,则崎岖度带来的额外时间花费为

《欧洲卡车模拟》虽然已经是九年前的游戏了,游戏内的风景却依旧惊艳。为了欣赏异国他乡的风景,小 Y 在运输的路途中可以在某个城市停留若干时间观光。

小 Y 现在新创建了一个人物开始游戏,假设她要从 号点运送货物到 号点,请你帮她求出所需要的最少时间。

输入格式

第一行两个正整数 ,表示点的个数和边的个数。

接下来 行,每行四个整数 ,分别表示道路连接的两个城市的编号,通过该道路的时间和道路的崎岖度。

输出格式

输出一行一个整数,表示从 行驶到 所需要的最短时间,若无法到达输出

样例

样例输入 1

2 1
1 2 2 3

样例输出 1

4

小 Y 在城市 停留 个单位时间,然后通过唯一的一条边,需要的时间为 ,总时间为

样例输入 2

2 3
1 2 2 3
1 2 2 1
1 1 1 1

样例输出 2

3

图中可能存在重边和自环。

样例输入 3

4 2
1 2 3 4
3 4 5 6

样例输出 3

-1

样例输入 4

6 9
1 1 0 0
1 3 1 2
1 5 2 3
5 2 16 5
2 6 1 10
3 4 3 4
3 5 3 10
5 6 1 100
4 2 0 110

样例输出 4

20

数据范围与提示

对于 的数据,

每个测试点的详细规模见下表:

测试点编号 特殊性质
图的形态是一棵树