Problem Description

This is a jungle where your friend, the chameleon, lives.

The jungle has $ N $ squares, numbered from $ 1 $ to $ N $. There are also $ M $ paths, numbered from $ 1 $ to $ M $. Each path connects two different squares and can be traversed in both directions.

Your friend, the chameleon, is trying to go from square $ 1 $ to square $ N $ to attend the CODE THANKS FESTIVAL 2015. The chameleon uses paths to move between squares. However, the paths in the jungle are filled with unknown dangers, so when using path $i\ (1\ ≦\ i\ ≦\ M)$, the chameleon's body color must be color $ c_i $. Also, moving through path $ i $ takes time $ t_i $.

The chameleon starts at square $ 1 $ with body color $ 1 $. The chameleon can change its body color at any square, but changing color from color $ x $ to color $ y $ takes time ｜$ x-y $｜. The chameleon ends its movement upon reaching square $ N $, and its body color at that time does not matter.

You are tasked with finding the minimum time it takes for the chameleon to reach square $ N $.

Input Format

The input is given from the standard input in the following format:

$ N $ $ M $ $ a_1 $ $ b_1 $ $ c_1 $ $ t_1 $ $ a_2 $ $ b_2 $ $ c_2 $ $ t_2 $ : $ a_M $ $ b_M $ $ c_M $ $ t_M $

• The first line contains the number of squares $N\ (2\ ≦\ N\ ≦\ 40,000)$ and the number of paths $M\ (1\ ≦\ M\ ≦\ 80,000)$, separated by spaces.
• The next $ M $ lines provide information about the paths. The $i\ (1\ ≦\ i\ ≦\ M)$-th line contains four integers $ a_i $, $b_i\ (1\ ≦\ a_i\ ＜\ b_i\ ≦\ N)$, $c_i\ (1\ ≦\ c_i\ ≦\ 1,000,000,000)$, $t_i\ (1\ ≦\ t_i\ ≦\ 1,000,000,000)$, separated by spaces. This indicates that path $ i $ connects squares $ a_i $ and $ b_i $, requires body color $ c_i $ to traverse, and takes time $ t_i $ to move through.
• If $ i $ ≠ $ j $, then $ a_i $ ≠ $ a_j $ or $ b_i $ ≠ $ b_j $ holds.
• It is guaranteed that you can travel from square $ 1 $ to any other square via at least one path.

Output Format

Output the minimum time it takes for the chameleon to reach square $ N $ on a single line. Ensure a newline at the end of the output.

Sample Input and Output

Sample Input #1

6 7
1 2 1 6
1 3 7 4
2 3 3 4
2 5 6 6
3 4 4 6
3 5 1 3
5 6 2 4

Sample Output #1

22

Sample Input #2

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

Sample Output #2

5

Notes/Hints

Sample Explanation 1

In this input example, the optimal movement is as follows:
- Initially, the chameleon is at square $ 1 $ with body color $ 1 $.
- Use path $ 1 $ to move from square $ 1 $ to square $ 2 $. Since the chameleon's body color is $ 1 $, it is possible to move, and the total time taken is $ 6 $.
- Change the body color from color $ 1 $ to color $ 3 $ at square $ 2 $. The total time taken is $ 6+2 $ = $ 8 $.
- Use path $ 3 $ to move from square $ 2 $ to square $ 3 $. Since the chameleon's body color is $ 3 $, it is possible to move, and the total time taken is $ 8+4 $ = $ 12 $.
- Change the body color from color $ 3 $ to color $ 1 $ at square $ 3 $. The total time taken is $ 12+2 $ = $ 14 $.
- Use path $ 6 $ to move from square $ 3 $ to square $ 5 $. Since the chameleon's body color is $ 1 $, it is possible to move, and the total time taken is $ 14+3 $ = $ 17 $.
- Change the body color from color $ 1 $ to color $ 2 $ at square $ 5 $. The total time taken is $ 17+1 $ = $ 18 $.
- Use path $ 7 $ to move from square $ 5 $ to square $ 6 $. Since the chameleon's body color is $ 2 $, it is possible to move, and the total time taken is $ 18+4 $ = $ 22 $.

见题面 Input 部分

见题面 Output 部分