背景

GESP七级真题(2603)

描述

一个物流网络由 $n$ 个城市和 $m$ 条双向公路组成。每条公路都有两个属性：

• 运输费用 $w_i$
• 景观评分 $b_i$

当一辆运输车从城市 1 运送货物到城市 $n$ 时，需要支付经过道路的运输费用之和。

为了推广旅游线路，物流公司推出了一项优惠政策：在运输路径上，可以免除景观评分最高的那条公路的运输费用。如果有多条公路的景观评分同为最大值，则只免除其中 一条 的费用。

请你计算，从城市 1 到城市 $n$ 的最小运输费用。

格式

输入

第一行两个整数 $n, m$ ，分别表示城市数量和公路数量。

接下来 $m$ 行，每行四个整数 $u, v, w, b$ ，表示存在一条连接城市 $u$ 和城市 $v$ 的双向公路，其中 $w$ 为运输费用， $b$ 为景观评分。

输出

输出一个整数，表示从城市 1 到城市 $n$ 的最小费用。

如果无法到达，输出 -1 。

样例

3 3
1 2 10 5
2 3 20 6
1 3 100 1

0

样例解释

路径 1->2->3：费用 10+20，最大美丽值 6 (边2-3)。免除 20，总花费 10。

路径 1->3：费用 100，最大美丽值 1 (边1-3)。免除 100，总花费 0。

最小费用为 0。

数据规模

$1 \le n \le 5000，1 \le w, b \le 10^9$。

限制

时间限制：1.0 s

空间限制：512.0 MB