Description

In order to get the true biography of the calligraphy masters, Xiao E made up his mind to visit the hermit who lived in the magical forest.

The magical forest can be seen as an undirected graph with $N$ Nodes and $M$ edges. The nodes are labeled $1,\ldots,N$ and the edges are labeled $1,\ldots,M$. At the beginning, Xiao E is at node labeled $1$ and the hermit lives at node labeled $N$. Xiao E needs to pass through the magical forest to be able to visit the hermit.

There are some monsters living in the magic forest. Whenever someone passes by an edge, the monsters on this edge will attack it. Fortunately, there are two kinds of guardian spirits living in node number $1$: $A$ Type guardian spirit and $B$ Type guardian spirit. Xiao E can use their power to achieve his goals.

As long as Xiao E brings enough guardian spirits, the monsters will not attack. Specifically, each edge in the undirected graph $E_i$ contains two weights $A_i$ and $B_i$. If the number of Type $A$ guardian spirits is not less than $A_i$ ,and the number of type $B$ guardian spirits is not less than $B_i$, the monsters on this edge will not attack people who pass this edge. If and only if in the process of passing through this magic forest, no monster attacks Xiao E, he can successfully find the hermit.

Since carrying guardian spirits is a very troublesome task, Xiao E wants to know that to be able to successfully visit the hermit, what is the minimum total number of guardian spirits he needs to carry. The total number of guardian spirits is the sum of the number of type $A$ guardian spirits and the number of type $B$ guardian spirits he is carrying.

Input Format

The first line contains two integers $N,M$, which means the undirected graph has $N$ Nodes and $M$ Edges. This is followed by $M$ lines, where $i$-th line contains four positive integers $X_i,Y_i,A_i,B_i$, describing the $i$-th edge, where $X_i$ and $Y_i$ are the labels of the two end points of the edge and $A_i$ and $B_i$ are as explained in the problem statement.

Note : The data may include heavy edges and self-loops.

Output Format

Output an integer on a line: if Xiao E can successfully visit the hermit, output the minimum total number of guardian spirits that Xiao E needs to carry. If Xiao E cannot visit the hermit in any way, output "-1" (without quotes).

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

Constraints

For all the data, $2 \leq n \leq 50000,\ 0 \leq m \leq 100000,\ 1 \leq a_i ,b_i \leq 50000$.