Problem Description

In the town of IOI, there are $ N $ intersections numbered from $ 1 $ to $ N $. There are also $ M $ roads numbered from $ 1 $ to $ M $. Each road connects two different intersections bidirectionally. Road $ i $ ($1 \leq i \leq M$) connects intersection $ A_i $ and intersection $ B_i $. No two different roads connect the same pair of intersections. Each road is painted with a color represented by an integer between $ 1 $ and $ M $, and the current color of road $ i $ is $ C_i $. Multiple roads may be painted the same color.

JOI Inc. has developed a robot that moves between intersections in the town of IOI. When you instruct the robot with a road color, it moves to an adjacent intersection through a road of the instructed color. However, if there are two or more roads of the instructed color connected to the intersection where the robot is currently located, the robot will stop because it cannot determine which road to take next.

Your goal is to move the robot, which is currently at intersection $ 1 $, to intersection $ N $ by giving it several instructions. However, this may not be possible with the current road colors, so you want to repaint some roads beforehand to ensure the robot can move to intersection $ N $. Road $ i $ ($1 \leq i \leq M$) can be repainted to any integer color between $ 1 $ and $ M $ for a cost of $ P_i $ yen.

Given the information about intersections and roads, create a program to find the minimum amount of money needed. If it is impossible to move the robot to intersection $ N $ regardless of how the roads are repainted, output -1 instead.

Input Format

The input is given from the standard input in the following format. All values are integers.

$ N $ $ M $ $ A_1 $ $ B_1 $ $ C_1 $ $ P_1 $ $\vdots$ $ A_M $ $ B_M $ $ C_M $ $ P_M $

Output Format

Output the minimum amount of money needed on a single line to the standard output. If it is impossible to move the robot to intersection $ N $ regardless of how the roads are repainted, output -1 instead.

Sample Input and Output

Sample Input #1

4 6
1 4 4 4
3 4 1 3
1 3 4 4
2 4 3 1
2 3 3 2
1 2 4 2

Sample Output #1

3

Sample Input #2

5 2
1 4 1 2
3 5 1 4

Sample Output #2

-1

Sample Input #3

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

Sample Output #3

1

Sample Input #4

13 21
7 10 4 4
3 6 4 7
8 10 4 5
3 9 2 5
1 4 4 5
2 6 4 2
3 11 2 2
3 8 16 2
8 11 16 1
6 10 4 14
6 8 16 6
9 12 16 5
5 13 4 6
1 12 4 7
2 4 4 18
2 9 4 10
2 12 4 6
10 13 4 28
5 7 2 5
5 11 2 16
7 13 4 20

Sample Output #4

7

Notes/Hints

Constraints

• $2 \leq N \leq 100,000$.
• $1 \leq M \leq 200,000$.
• $1 \leq A_i < B_i \leq N$ ($1 \leq i \leq M$).
• $(A_i, B_i) \neq (A_j, B_j)$ ($1 \leq i < j \leq M$).
• $1 \leq C_i \leq M$ ($1 \leq i \leq M$).
• $1 \leq P_i \leq 1,000,000,000$ ($1 \leq i \leq M$).

Subtasks

1. ($ 34 $ points) $N \leq 1,000$, $M \leq 2,000$.
2. ($ 24 $ points) $ P_i = 1 $ ($1 \leq i \leq M$).
3. ($ 42 $ points) No additional constraints.

Sample Explanation 1

Repaint road $ 4 $ from color $ 3 $ to color $ 4 $ for $ 1 $ yen, and road $ 6 $ from color $ 4 $ to color $ 2 $ for $ 2 $ yen. The total cost is $ 3 $ yen. As a result, the robot at intersection $ 1 $ can be moved to intersection $ 2 $ by instructing color $ 2 $, and then to intersection $ 4 $ by instructing color $ 4 $. It is impossible to move the robot to intersection $ 4 $ for $ 2 $ yen or less, so output $ 3 $.

Sample Explanation 2

Regardless of how the roads are repainted, it is impossible to move the robot to intersection $ 5 $. Therefore, output -1.

Sample Explanation 3

This input example satisfies the constraints of subtask $ 2 $.

见题面 Input 部分

见题面 Output 部分