物流⽹络

题目描述

⼀个物流⽹络由 个城市和 条双向公路组成。每条公路都有两个属性： 运输费⽤ 景观评分 当⼀辆运输车从城市 运送货物到城市 时，需要⽀付经过道路的运输费⽤之和。 为了推⼴旅游线路，物流公司推出了⼀项优惠政策：在运输路径上，可以免除景观评分最⾼的那条公路的运输费 ⽤。如果有多条公路的景观评分同为最⼤值，则只免除其中 ⼀条 的费⽤。 请你计算，从城市 到城市 的最⼩运输费⽤。

输入格式

第⼀⾏两个整数 ，分别表⽰城市数量和公路数量。 接下来 ⾏，每⾏四个整数 ，表⽰存在⼀条连接城市 和城市 的双向公路，其中 为运输费⽤， 为景 观评分。

输出格式

输出⼀个整数，表⽰从城市 到城市 的最⼩费⽤。 如果⽆法到达，输出 -1。

样例输入 #1

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

样例输出 #1

0

样例解释 #1

路径 ：费⽤ ，最⼤美丽值 6 (边 )。免除 ，总花费 。 路径 ：费⽤ ，最⼤美丽值 1 (边 )。免除 ，总花费 。 最⼩费⽤为 。

数据范围

， 。

知识点与难度

本题涉及的知识点从属于 GESP 7级，难度等级：⭐⭐⭐⭐⭐⭐ 。

测试点分布

生测试数据后，按实际 subtask 分组改写上表。