题目描述

某座城市有 $n$ 个十字路口，通过 $m$ 段道路相互连接，构成了城市的交通网络。每段道路连接两个不同的路口，且道路之间不会在中途交叉。

由于施工安全等原因，部分道路的中间安装了限高杆，大型货车无法通行这些路段。

城市中有两个重要的物流中心 $A$ 和 $B$，分别紧邻路口 $1$ 和路口 $n$。货车从 $A$ 出发，先到达路口 $1$，再通过交通网络行驶至路口 $n$，最终抵达 $B$。这两个物流中心之间每天有大量货车往返运输货物。

交通部门发现，由于限高杆的存在，货车不得不绕行很远的路线，这不仅增加了道路磨损，还提高了运输成本和碳排放。

交通部门计划拆除恰好两段道路上的限高杆，使得货车从 $A$ 到 $B$ 的最短行驶距离尽可能缩短。请问最多能缩短多少距离？

输入格式

输入第一行包含两个整数 $n$ 和 $m$，分别表示路口数量和道路段数。

接下来 $m$ 行，每行四个整数 $a$、$b$、$c$、$d$，表示路口 $a$ 和路口 $b$ 之间有一段长度为 $c$ 的道路。若 $d$ 为 $0$，表示该道路无限高杆，货车可正常通行；若 $d$ 为 $1$，表示该道路有限高杆，货车无法通过。两个路口之间可能存在多段道路。

输入数据保证在不拆除任何限高杆的情况下，货车能够从路口 $1$ 行驶到路口 $n$。

输出格式

输出一行，包含一个整数，表示拆除两段道路的限高杆后，从 $A$ 到 $B$ 的最短行驶距离最多能缩短多少。

样例

5 7
1 2 1 0
2 3 2 1
1 3 9 0
5 3 8 0
4 3 5 1
4 3 9 0
4 5 4 0

6

提示

【样例说明】

原图中只有两段道路有限高杆，全部拆除后，$1$ 到 $n$ 的最短路径从 $17$ 变为 $11$，减少了 $6$。

【评测用例规模与约定】

对于 $30\%$ 的评测用例，$2 \leq n \leq 10$，$1 \leq m \leq 20$，$1 \leq c \leq 100$。

对于 $50\%$ 的评测用例，$2 \leq n \leq 100$，$1 \leq m \leq 1000$，$1 \leq c \leq 1000$。

对于 $70\%$ 的评测用例，$2 \leq n \leq 1000$，$1 \leq m \leq 10000$，$1 \leq c \leq 10000$。

对于所有评测用例，$2 \leq n \leq 10000$，$2 \leq m \leq 10^5$，$1 \leq c \leq 10000$，至少有两段道路有限高杆。