物流网络

题目描述

一个物流网络由 n 个城市和 m 条双向公路组成。每条公路都有两个属性：运输费用 w，景观评分 b。 当一辆运输车从城市 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

数据范围

保证 2 ≤ n ≤ 1000，1 ≤ m ≤ 1500，1 ≤ u, v ≤ n，1 ≤ w ≤ 10000，1 ≤ b ≤ 10000。