### 问题描述
某市有 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≤n≤10,1≤m≤20,1≤c≤100 。
对于 50% 的评澍样例, 2≤n≤100,1≤m≤1000,1≤c≤1000 。
对于 70% 的评测样例, 2≤n≤1000,1≤m≤10000,1≤c≤10000 。
对于所有评测样例, 2≤n≤10000,2≤m≤100000,1≤c≤10000, 至多有两段道珞有眼高杆。