To receive the true teachings of a calligraphy master, student E is determined to visit a hermit living in the Magic Forest. The Magic Forest can be viewed as an undirected graph containing $n$ nodes and $m$ edges, with nodes labeled $1, 2, 3, \dots, n$ and edges labeled $1, 2, 3, \dots, m$. Initially, student E is at node $1$, and the hermit lives at node $n$. Student E must pass through this Magic Forest to visit the hermit.

Some monsters live in the Magic Forest. Whenever someone passes through an edge, the monsters on that edge will attack them. Fortunately, there are two types of guardian spirits living at node $1$: Type A guardian spirits and Type B guardian spirits. Student E can use their power to achieve his goal.

As long as student E carries enough guardian spirits, the monsters will not attack. Specifically, each edge in the undirected graph contains two values, $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 the person passing through it. Student E can successfully find the hermit if and only if no monsters on any edge attack him during his journey through the Magic Forest.

Since carrying guardian spirits is very troublesome, student E wants to know the minimum total number of guardian spirits he needs to carry to successfully visit the hermit. 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.

Input

The first line of the input contains two integers $n$ and $m$, representing that the undirected graph has $n$ nodes and $m$ edges.

The next $m$ lines each contain 4 positive integers $X_i, Y_i, a_i, b_i$, describing 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 in the problem.

Note that the data may contain multiple edges and self-loops.

Output

Output a single integer: if student E can successfully visit the hermit, output the minimum total number of guardian spirits student E needs to carry; if student E cannot visit the hermit under any circumstances, output "-1" (without quotes).

Examples

Input 1

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

Output 1

32

Note 1

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

Input 2

3 1
1 2 1 1

Output 2

-1

Note 2

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

Constraints