Minimize Cycle Cost with Single Edge Reversal

You are given a directed graph with \(N\) vertices and \(M\) directed edges. Each edge \(i\) goes from \(U_i\) to \(V_i\) with a cost of \(C_i\). You are also allowed to reverse at most one edge. When you reverse edge \(i\) (i.e. change its direction from \(U_i \to V_i\) to \(V_i \to U_i\)), an extra cost \(D_i\) is incurred.

Your task is to find the minimum total cost to travel from vertex 1 to vertex \(N\) and then to travel back from vertex \(N\) to vertex 1. You may choose to reverse one edge in either the forward leg (from 1 to \(N\)) or the backward leg (from \(N\) to 1), or not use any reversal at all.

Let:

• \(d(1,x)\) be the minimum cost from vertex 1 to vertex \(x\) in the original graph.
• \(d(x,N)\) be the minimum cost from vertex \(x\) to vertex \(N\) in the original graph.
• \(d(N,x)\) be the minimum cost from vertex \(N\) to vertex \(x\) in the original graph.
• \(d(x,1)\) be the minimum cost from vertex \(x\) to vertex 1 in the original graph.

The answer is the minimum among the following three options:

1. No reversal: \(\text{cost} = d(1,N) + d(N,1)\).
2. Using reversal in the forward leg: For some edge \(i\), the forward path becomes: 1 \(\to\) \(V_i\) (cost \(d(1,V_i)\)), then the reversed edge \(V_i \to U_i\) (with cost \(D_i\)), then \(U_i \to N\) (cost \(d(U_i,N)\)). The overall cost is \(d(1,V_i) + D_i + d(U_i,N) + d(N,1)\).
3. Using reversal in the backward leg: For some edge \(i\), the backward path becomes: \(N \to V_i\) (cost \(d(N,V_i)\)), then the reversed edge \(V_i \to U_i\) (with cost \(D_i\)), then \(U_i \to 1\) (cost \(d(U_i,1)\)). The overall cost is \(d(1,N) + d(N,V_i) + D_i + d(U_i,1)\).

If a required path does not exist, it is considered to have an infinite cost. Output the minimum total cost if a solution exists, or -1 otherwise.

inputFormat

The first line contains two integers \(N\) and \(M\) (\(2 \leq N \leq 10^5,\ 1 \leq M \leq 2 \times 10^5\)). Each of the next \(M\) lines contains four integers \(U_i\), \(V_i\), \(C_i\), and \(D_i\) (\(1 \leq U_i, V_i \leq N;\ 1 \leq C_i, D_i \leq 10^9\)), describing an edge from \(U_i\) to \(V_i\) with cost \(C_i\) and the reversal cost \(D_i\).

outputFormat

Output a single integer, representing the minimum total cost to travel from vertex 1 to vertex \(N\) and back to vertex 1, using at most one edge reversal. If it is impossible to complete the journey, output -1.

sample

3 3
1 2 3 10
2 3 4 1
3 1 5 2

7