在 IOI 镇上有 $N$ 个路口，编号为 $1$ 到 $N$。有 $M$ 条道路，编号为 $1$ 到 $M$。 每条道路连接两个不同的路口，且是双向的。第 $i$ 条道路 ($1 \le i \le M$) 连接路口 $A_i$ 和路口 $B_i$。没有两条不同的道路连接同一对路口。每条道路都有一个颜色，用 $1$ 到 $M$ 之间的整数表示。目前，第 $i$ 条道路的颜色为 $C_i$。多条道路可能具有相同的颜色。

JOI 有限公司开发了一种在 IOI 镇路口间移动的机器人。每当你告诉机器人一个颜色时，机器人会找到该颜色的道路，然后通过它移动到相邻的路口。然而，如果当前路口连接了多条该颜色的道路，机器人将无法决定应该通过哪条道路，从而停止移动。

机器人目前位于路口 $1$。你的任务是通过告诉机器人一系列颜色，将其移动到路口 $N$。然而，机器人并不总是能移动到路口 $N$。你可以提前更改某些道路的颜色，以便机器人能够移动到路口 $N$。将第 $i$ 条道路 ($1 \le i \le M$) 的颜色更改为 $1$ 到 $M$ 之间的任意颜色，其费用为 $P_i$ 日元。

编写一个程序，在给定路口和道路信息的情况下，计算最小总费用。如果即使更改了道路颜色也无法将机器人移动到路口 $N$，则输出 $-1$。

输入格式

从标准输入读取以下数据。给定值均为整数。

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

输出格式

将结果输出到标准输出。输出应包含最小总费用。如果即使更改了道路颜色也无法将机器人移动到路口 $N$，则输出 $-1$。

数据范围

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

子任务

1. (34 分) $N \le 1\,000, M \le 2\,000$
2. (24 分) $P_i = 1$ ($1 \le i \le M$)
3. (42 分) 无附加限制

样例

样例输入 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

样例输出 1

3

说明 1

你可以花费 $1$ 日元将第 $4$ 条道路的颜色从 $3$ 改为 $4$。你可以花费 $2$ 日元将第 $6$ 条道路的颜色从 $4$ 改为 $2$。总费用为 $3$ 日元。 之后，你告诉机器人颜色 $2$，它从路口 $1$ 移动到路口 $2$。然后，你告诉机器人颜色 $4$，它移动到路口 $4$。 支付少于 $3$ 日元无法使机器人移动到路口 $4$。因此输出 $3$。

样例输入 2

5 2
1 4 1 2
3 5 1 4

样例输出 2

-1

说明 2

即使更改道路颜色，也无法将机器人移动到路口 $5$。因此输出 $-1$。

样例输入 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

样例输出 3

1

说明 3

此样例输入满足子任务 $2$ 的限制。

样例输入 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

样例输出 4

7