Background

Related multiple-choice and true/false questions: https://ti.luogu.com.cn/problemset/1211.

Problem Description

A logistics network consists of $n$ cities and $m$ bidirectional roads. Each road has two attributes:

• Transport cost $w_i$.
• Scenic rating $b_i$.

When a truck transports goods from city $1$ to city $n$, it needs to pay the sum of the transport costs of the roads it travels on.

To promote tourist routes, the logistics company offers a discount policy: along the transport path, the transport cost of the road with the highest scenic rating can be waived. If there are multiple roads whose scenic rating ties for the maximum, only the cost of one of them is waived.

Please compute the minimum transport cost from city $1$ to city $n$.

Input Format

The first line contains two integers $n, m$, representing the number of cities and the number of roads.

The next $m$ lines each contain four integers $u, v, w, b$, indicating a bidirectional road connecting city $u$ and city $v$, where $w$ is the transport cost and $b$ is the scenic rating.

Output Format

Output one integer, representing the minimum cost from city $1$ to city $n$.

If city $n$ cannot be reached, output -1.

3 3
1 2 10 5
2 3 20 6
1 3 100 1

0

Hint

Sample Explanation

Path $1\to 2\to 3$: cost $10+20$, maximum scenic rating $6$ (edge $2-3$). Waive $20$, total cost $10$.

Path $1\to 3$: cost $100$, maximum scenic rating $1$ (edge $1-3$). Waive $100$, total cost $0$.

Constraints

$1\leq n\leq 5000$, $1\leq m\leq 5000$, $1\leq w,b\leq 10^9$.

Translated by ChatGPT 5