Problem Description

A certain city has $n$ intersections and $m$ road segments connecting these intersections, forming the city's road system. Each road segment connects two different intersections. Roads do not pass through any intersection in the middle.

For various reasons, some road segments have height-limit bars installed in the middle. Trucks cannot pass through road segments that have height-limit bars.

There are two important markets, $A$ and $B$, located near intersections $1$ and $n$ respectively. A truck departs from market $A$, first goes to intersection $1$, then travels through the road system to reach intersection $n$, and only then can it arrive at market $B$. Both markets are very busy, and many trucks travel back and forth between them every day.

The mayor found that because there are many height-limit bars, trucks may need to take detours to travel between the markets. This makes the driving distance within the road system longer, increasing wear on the road system, increasing energy consumption, and also increasing environmental pollution.

The mayor decided to remove the height-limit bars on two road segments to shorten the distance between markets $A$ and $B$. What is the maximum distance that can be reduced?

Input Format

The first line contains two integers $n$ and $m$, representing the number of intersections and the number of road segments.

The next $m$ lines each contain four integers $a$, $b$, $c$, $d$, indicating that there is a road segment of length $c$ between intersections $a$ and $b$. If $d$ is $0$, it means there is no height-limit bar on this road segment; if $d$ is $1$, it means there is a height-limit bar on this road segment. There may be multiple road segments between the same pair of intersections.

The input guarantees that without removing any height-limit bars, trucks can normally travel through the road system from intersection $1$ to intersection $n$.

Output Format

Output one line containing one integer, which is the maximum distance by which the route between markets $A$ and $B$ can be reduced after removing the height-limit bars on two road segments.

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

Hint

Sample Explanation

There are only two road segments with height-limit bars. After removing them all, the distance from $1$ to $n$ changes from $17$ to $11$, a reduction of $6$.

Constraints and Conventions

For $30\%$ of the testdata, $2 \leq n \leq 10$, $1 \leq m \leq 20$, $1 \leq c \leq 100$.

For $50\%$ of the testdata, $2 \leq n \leq 100$, $1 \leq m \leq 1000$, $1 \leq c \leq 1000$.

For $70\%$ of the testdata, $2 \leq n \leq 1000$, $1 \leq m \leq 10000$, $1 \leq c \leq 10000$.

For all testdata, $2 \leq n \leq 10000$, $2 \leq m \leq 10^5$, $1 \leq c \leq 10000$, and there are at least two road segments with height-limit bars.

Lanqiao Cup 2020, Third Round Provincial Contest, AB Group, Problem H.

Translated by ChatGPT 5