题目描述

译自 JOI 2021 Final T4「ロボット / Robot」

在 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$；

接下来 $M$ 行，每行四个整数 $A_i, B_i, C_i, P_i$，表示第 $i$ 条路连接的两个路口 $A_i$ 和 $B_i$，当前颜色为 $C_i$，改变颜色的花费为 $P_i$。

---

输出格式

输出一行一个整数，表示最小总花费。如果通过改变道路颜色也不能使得机器人移动到路口 $N$，则输出 $-1$。

---

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

你可以花费 $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

输出

-1

即使改变路的颜色，也无法使得机器人移向路口 $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

输出

1

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

---

数据范围与提示

对于所有数据，满足：

• $2 \le N \le 10^5$；
• $1 \le M \le 2 \times 10^5$；
• $1 \le A_i < B_i \le N$ $(1 \le i \le N)$；
• $(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 10^9$ $(1 \le i \le M)$。

详细子任务附加限制及分值如下：

子任务编号	附加限制	分值
1	$N \le 1\,000$, $M \le 2\,000$	34
2	$P_i = 1$ $(1 \le i \le M)$	24
3	无附加限制	42

---