Description

To receive the true teachings of a calligraphy master, Xiao E has decided to visit a hermit who lives in the Magic Forest. The Magic Forest can be regarded as an undirected graph with $n$ nodes and $m$ edges. The nodes are labeled $1, 2, 3, \dots, n$, and the edges are labeled $1, 2, 3, \dots, m$. Initially, Xiao E is at node $1$, and the hermit lives at node $n$. Xiao E needs to pass through this Magic Forest to visit the hermit.

There are some monsters living in the Magic Forest. Whenever someone passes an edge, the monsters on that edge will launch an attack. Fortunately, two kinds of guardian spirits live at node $1$: A-type guardian spirits and B-type guardian spirits. Xiao E can rely on their power to achieve his goal.

As long as Xiao E brings enough guardian spirits, the monsters will not attack. Specifically, each edge $e_i$ in the undirected graph has two weights $a_i$ and $b_i$. If the number of A-type guardian spirits carried is at least $a_i$, and the number of B-type guardian spirits carried is at least $b_i$, then the monsters on this edge will not attack people who pass through this edge. Xiao E can successfully find the hermit if and only if, during the traversal of the Magic Forest, the monsters on no edge launch an attack on him.

Since carrying guardian spirits is very troublesome, Xiao E wants to know the minimum total number of guardian spirits required to successfully visit the hermit. The total number of guardian spirits is the sum of the number of A-type guardian spirits and B-type guardian spirits.

Input Format

The first line of the input file contains two integers $n, m$, indicating that the undirected graph has $n$ nodes and $m$ edges. The next $m$ lines, where the $(i+1)$-th line contains $4$ positive integers $X_i, Y_i, a_i, b_i$, describe the $i$-th undirected edge. Here, $X_i$ and $Y_i$ are the labels of the two endpoints of the edge, and $a_i$ and $b_i$ have the meanings described above. Note that the testdata may contain multiple edges and self-loops.

Output Format

Output one line with one integer: if Xiao E can successfully visit the hermit, output the minimum total number of guardian spirits Xiao E needs to carry; if Xiao E cannot visit the hermit under any circumstances, output -1.

4 5 
1 2 19 1 
2 3 8 12 
2 4 12 15 
1 3 17 8 
3 4 1 17 

32

3 1 
1 2 1 1 

-1

Hint

• Explanation 1

If Xiao E takes the path $1\to 2\to 4$, he needs to carry $19+15=34$ guardian spirits; if Xiao E takes the path $1\to 3\to 4$, he needs to carry $17+17=34$ guardian spirits; if Xiao E takes the path $1\to 2\to 3\to 4$, he needs to carry $19+17=36$ guardian spirits; if Xiao E takes the path $1\to 3\to 2\to 4$, he needs to carry $17+15=32$ guardian spirits. In summary, Xiao E needs to carry at least $32$ guardian spirits.

• Explanation 2

Xiao E cannot reach node $3$ from node $1$, so output -1.

Translated by ChatGPT 5