题目描述

一个物流网络由 $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\to 2\to 3$：费用 $10+20=30$，景观评分最大值 $6$（边 $2-3$），免除 $20$，总花费 $10$。
• 路径 $1\to 3$：费用 $100$，景观评分最大值 $1$（边 $1-3$），免除 $100$，总花费 $0$。
  最小费用为 $0$。

数据范围

• $1 \le n \le 5000$
• $1 \le m \le 5000$
• $1 \le w, b \le 10^9$，输入均为整数。