Description

Keke and Kaka live in the eastern suburbs of HF City. Every day, they have to transfer several times to reach their school at the western end of the city. One day, after joining the school's informatics olympiad group, they realized that their daily commuting route might not be optimal.

Keke: "We might be wasting a lot of time on the way to school. Let's write a program to compute the minimum time needed!"

HF City has $N$ bus stops, numbered from $1$ to $N$. Assume Keke and Kaka live near stop $1$, and their school is at stop $N$. There are $M$ direct bus routes in the city. For the $i$-th route, buses shuttle back and forth between stops $p_i$ and $q_i$, and the time from one endpoint to the other is $t_i$ ( $1 \leq i \leq M$, $1 \leq p_i, q_i \leq N$ ).

They quickly wrote a program to compute the optimal commuting plan. However, Keke suddenly had a mischievous idea: he wanted to delete some routes from Kaka’s input data so that Kaka’s program would output an answer larger than the true shortest time. Each route $i$ has a cost $c_i$: the larger $c_i$ is, the easier it is for Kaka to notice the prank. Keke wants to know how to choose routes to delete so that the minimum time from home to school increases, while the sum of $c_i$ of the deleted routes is minimized.

Write a program to:

• Read the bus network of HF City from the input file.
• Compute the actual minimum time needed for Keke and Kaka to get to school.
• Help Keke design a deletion plan: remove some bus routes from the input so that the minimum time from home to school becomes larger after deletion, and the sum of $c_i$ of the deleted routes is minimized.
• Output the answers.

Input Format

The first line contains two positive integers $N$ and $M$, the number of bus stops and direct bus routes in HF City.

Each of the next $M$ lines (the $i$-th of these lines is overall line $(i+1)$) describes the $i$-th route with four positive integers $p_i, q_i, t_i, c_i$, as defined above.

Output Format

The first line contains a single integer, the minimum time needed to travel from Keke and Kaka’s home to their school.

The second line contains a single integer $C$, the sum of $c_i$ of the deleted routes.

6 7 
1 2 1 3 
2 6 1 5 
1 3 1 1 
3 4 1 1 
4 6 1 1 
5 6 1 2 
1 5 1 4

2
5

Hint

$2 \leq N \leq 500$, $1 \leq M \leq 124750$, $1 \leq t_i, c_i \leq 10^4$.

HF City’s bus network is very well connected; you may assume any two stops are mutually reachable via direct routes or transfers. Of course, if under your deletion plan the home and school become disconnected, then the minimum time is considered to be $+\infty$. This is a valid plan.

Translated by ChatGPT 5