Problem Description

To receive the true teachings of a renowned calligrapher, Little E has decided to visit a hermit living in the Magic Forest. The Magic Forest can be considered as an undirected graph containing $n$ nodes and $m$ edges, with node labels ranging from $1$ to $n$ and edge labels from $1$ to $m$. Initially, Little E is at node $1$, while the hermit resides at node $n$. Little E needs to traverse this Magic Forest to meet the hermit.

The Magic Forest is inhabited by some monsters. Whenever someone passes an edge, the monsters on that edge attack them. Fortunately, node $1$ is home to two types of guardian spirits: Type A and Type B. Little E can use their power to achieve his goal.

As long as Little E carries 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 Type A guardian spirits carried is at least $a_i$, and the number of Type B guardian spirits is at least $b_i$, the monsters on that edge will not attack. Little E can only successfully find the hermit if no monsters attack him during his traversal of the Magic Forest.

Since carrying guardian spirits is cumbersome, Little E wants to know the minimum total number of guardian spirits needed to successfully visit the hermit. The total number of guardian spirits is the sum of the Type A and Type B guardian spirits.

Input Format

The first line of the input file contains two integers $n$ and $m$, representing the number of nodes and edges in the undirected graph, respectively. The next $m$ lines, with the $i+1$-th line containing four 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$ are as described in the problem. Note that the data may include duplicate edges and self-loops.

Output Format

Output a single integer: If Little E can successfully visit the hermit, output the minimum total number of guardian spirits he needs to carry; if it is impossible for Little E to visit the hermit, output -1.

Sample Input and Output

Input Sample #1

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

Output Sample #1

32

Input Sample #2

3 1 
1 2 1 1 

Output Sample #2

-1

Notes

• Explanation 1

If Little E takes the path $1 \to 2 \to 4$, he needs to carry $19 + 15 = 34$ guardian spirits; if he takes the path $1 \to 3 \to 4$, he needs to carry $17 + 17 = 34$ guardian spirits; if he takes the path $1 \to 2 \to 3 \to 4$, he needs to carry $19 + 17 = 36$ guardian spirits; if he takes the path $1 \to 3 \to 2 \to 4$, he needs to carry $17 + 15 = 32$ guardian spirits. Therefore, the minimum number of guardian spirits Little E needs to carry is $32$.

• Explanation 2

Little E cannot reach node $3$ from node $1$, so the output is -1.

见题面 Input 部分

见题面 Output 部分