Bobo lives in the big city of ICPCCamp.

ICPCCamp has $n$ subway stations, numbered $1, 2, \dots, n$. There are $m$ bidirectional subway lines connecting the $n$ stations. The $i$-th subway line belongs to route $c_i$ and connects stations $a_i$ and $b_i$. Traveling between $a_i$ and $b_i$ takes $t_i$ minutes in either direction (i.e., it takes $t_i$ minutes to go from $a_i$ to $b_i$, and $t_i$ minutes to go from $b_i$ to $a_i$).

As everyone knows, transferring between lines is troublesome. If you arrive at a subway station $s$ via the $i$-th subway line and depart from station $s$ via the $j$-th subway line, you must spend an additional $|c_i - c_j|$ minutes. Note that transfers can only occur within subway stations.

Bobo wants to know the minimum time required to travel from subway station $1$ to subway station $n$.

Input

The input contains no more than $20$ test cases.

The first line of each test case contains two integers $n, m$ ($2 \leq n \leq 10^5, 1 \leq m \leq 10^5$).

Each of the next $m$ lines contains four integers $a_i, b_i, c_i, t_i$ ($1 \leq a_i, b_i, c_i \leq n, 1 \leq t_i \leq 10^9$).

It is guaranteed that there exists a path from subway station $1$ to $n$ (not necessarily direct).

Output

For each test case, output a single integer representing the required minimum time.

Examples

Input 1

3 3
1 2 1 1
2 3 2 1
1 3 1 1
3 3
1 2 1 1
2 3 2 1
1 3 1 10
3 2
1 2 1 1
2 3 1 1

Output 1

1
3
2