Description

There are $N$ crossings in the IOI town, numbered from $1$ to $N$. There are $M$ roads, numbered from $1$ to $M$.

Each road connects two different crossings in both directions. The road $i$ ($1 \leq i \leq M$) connects the crossing $A_i$ and the crossing $B_i$. No two different roads connect the same pair of crossings. Each of the roads has a color, which is described as an integer between $1$ and $M$, inclusive. Currently, the color of the road $i$ is $C_i$. More than one road may have the same color.

The JOI Co., Ltd. developed a robot moving around the crossings of the IOI town. Whenever you tell a color to the robot, the robot will find the road with that color, and then the robot will pass through it and moves to the adjacent crossing. However, if there are more than one roads with the told color connected to the current crossing of the robot, it cannot decide which road it should pass through, and will halt.

The robot is currently in the crossing $1$. Your task is to move the robot to the crossing $N$ by telling colors to it. However, it is not always true that the robot can be moved to the crossing $N$. You may change the colors of some of the roads in advance so that the robot can be moved to the crossing $N$. It costs $P_i$ yen to change the color of the road $i$ ($1 \leq i \leq M$) to any color between $1$ and $M$, inclusive.

Write a program which, given the information of the crossings and the roads, calculates the minimum total cost. However, if it is impossible to move the robot to the crossing N even if you change the colors of the roads, output -1 instead.

Input

Read the following data from the standard input. Given values are all integers.

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

Output

Write one line to the standard output. The output should contain the minimum total cost. However, if it is impossible to move the robot to the crossing $N$ even if you change the colors of the roads, output -1 instead.

Sample 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

3

You can change the color of the road $4$ from color $3$ to color $4$ at the cost of $1$ yen. You can change the color of the road $6$ from color $4$ to color $2$ at the cost of $2$ yen. The total cost is $3$ yen.

After that, you tell the color $2$ to the robot, then it moves from the crossing $1$ to the crossing $2$. And, you tell the color $4$ to the robot, then it moves to the crossing $4$.

It is impossible to pay less than $3$ yen so that the robot can be moved to the crossing $4$. Hence output $3$.

5 2
1 4 1 2
3 5 1 4

-1

It is impossible to move the robot to the crossing $5$ even if you change the colors of the roads. Hence output -1.

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

1

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

Constraints

• $2 \leq N \leq 10^5$.
• $1 \leq M \leq 2 \times 10^5$.
• $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 10^9$ ($1 \leq i \leq M$).

Subtasks

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