Given a graph having N vertices and M bidirectional edges, with each edge having some length and some destruction cost. You have to increase the length of the shortest path between vertex 1 and vertex N, for that you can destroy some edges. Find the minimum cost of doing it.
Input Format:
First line consists of two space separated integers denoting N and M.
Following M lines consists of four space separated integers \(X \; Y \; D \; C\) denoting that there is an edge between vertex X and Y having length D and destruction cost C.
Output Format:
Print the required answer.
Constraints:
\(2 \le N \le 1000\)
\(1 \le M \le 4 \times 10^5\)
\(1 \le X, Y \le N\)
\(1 \le D, C \le 1000000\)
4 6 1 2 4 1 1 3 8 6 1 4 1 8 2 3 8 8 2 4 5 7 3 4 7 5
8
Currently the shortest path between 1 and 4 is of length 1, so we delete this vertex at a cost of 8, so that the length of shortest path increases to 9.
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor
Login to unlock the editorial
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor