时间限制：1.0 s
内存限制：512.0 MB

题目描述

一个物流网络由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≤n≤5000, 1≤m≤5000，1≤w,b≤10⁹。