Maximizing Distance Reduction in a Road Network

A city has \(n\) intersections and \(m\) roads connecting them. Each road connects two distinct intersections and does not pass through any other intersection. Some roads have height barriers installed in the middle, which prevent trucks from passing through.

There are two major markets, \(A\) and \(B\), located near intersections \(1\) and \(n\) respectively. Trucks start from market \(A\), first reaching intersection \(1\), then traveling through the road network to reach intersection \(n\) (and finally market \(B\)). Due to many height barriers, trucks may be forced to take a longer detour, increasing fuel consumption and road wear.

The mayor has decided to remove the height barriers on two roads in order to potentially reduce the travel distance between markets \(A\) and \(B\). Determine the maximum decrease in distance that can be achieved by optimally removing the barriers on two roads. In other words, let \(D_0\) be the shortest distance from intersection \(1\) to \(n\) when only roads without barriers (\(t = 0\)) are used, and let \(D\) be the shortest distance when you are allowed to use at most two roads that originally have barriers (i.e. with \(t = 1\), after removal) in addition to the barrier‐free roads. Output \(\max(0, D_0 - D)\).

You can assume that there is a valid route in the original road network (using non–barrier roads) from intersection \(1\) to intersection \(n\).

inputFormat

The input is given as follows:

 n m
 u1 v1 d1 t1
 u2 v2 d2 t2
 ...
 um vm dm tm

Where:

• \(n\) is the number of intersections \((2 \le n \le 10^5)\).
• \(m\) is the number of roads \((1 \le m \le 2 \times 10^5)\).
• Each road is described by four integers \(u, v, d, t\), meaning there is a road between intersections \(u\) and \(v\) with length \(d\) (\(1 \le d \le 10^5\)), and \(t\) indicates whether the road has a height barrier (\(t = 1\)) or not (\(t = 0\)).
• The roads are bidirectional and no road connects an intersection to itself.

outputFormat

Output a single integer representing the maximum distance reduction achievable by removing the height barriers from two roads optimally. If no improvement is possible, output 0.

sample

4 5
1 2 3 0
2 4 5 0
1 3 2 1
3 4 2 1
2 3 1 0

4