A67867. 物流网络

试题名称：物流网络 

时间限制：1.0 s 

内存限制：512.0 MB 

3.2.1 题目描述 

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

运输费用w_i

景观评分b_i

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

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

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

3.2.2 输入格式 

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

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

3.2.3 输出格式 

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

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

3.2.4 样例 

3.2.4.1 输入样例 

3.2.4.2 输出样例 

3.2.5 样例解释 

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

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

最小费用为 0。 

3.2.6 数据范围 

1≤n≤5000,1≤m≤5000，1≤w,b≤10⁹ 。