IOI 町有 $N$ 个交叉路口，编号从 $1$ 到 $N$。此外，有 $M$ 条道路，编号从 $1$ 到 $M$。每条道路连接两个不同的交叉路口，且是双向的。第 $i$ 条道路（$1 \leq i \leq M$）连接交叉路口 $A_i$ 和 $B_i$。不会有两条不同的道路连接同一对交叉路口。这些道路被涂上了 $1$ 到 $M$ 之间的某种颜色，第 $i$ 条道路当前的颜色为 $C_i$。可能有多条道路被涂成相同的颜色。

JOI 公司开发了一种能在 IOI 町的交叉路口间移动的机器人。你可以向机器人下达颜色指令，机器人会沿着与该颜色相同的道路移动到相邻的交叉路口。但是，如果机器人当前所在的交叉路口有两条或以上与指示颜色相同的道路，则机器人无法判断该走哪一条路，会停止移动。

你的目标是通过若干次指令，让当前在交叉路口 $1$ 的机器人移动到交叉路口 $N$。但以当前的道路颜色，不一定能实现这一目标，因此你可以事先将一些道路重新涂色，使得机器人能够到达交叉路口 $N$。第 $i$ 条道路（$1 \leq i \leq M$）可以花费 $P_i$ 日元重新涂成 $1$ 到 $M$ 之间任意一种颜色。

给定交叉路口和道路的信息，请编写程序求出所需的最小花费。如果无论如何重新涂色都无法让机器人到达交叉路口 $N$，则输出 $-1$。

输入以如下格式从标准输入读入。所有输入值均为整数。

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

请在一行中输出所需的最小花费。如果无论如何重新涂色都无法让机器人到达交叉路口 $N$，则输出 $-1$。

限制条件

• $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$）。

子任务

1.（34 分）$N \leq 1\,000$，$M \leq 2\,000$。
2.（24 分）$P_i = 1$（$1 \leq i \leq M$）。
3.（42 分）无额外限制。

样例说明 1

将第 $4$ 条道路从颜色 $3$ 重新涂为颜色 $4$，花费 $1$ 日元；将第 $6$ 条道路从颜色 $4$ 重新涂为颜色 $2$，花费 $2$ 日元。总共花费 $3$ 日元。这样，机器人在交叉路口 $1$ 时，指示颜色 $2$，机器人可以移动到交叉路口 $2$。接着，指示颜色 $4$，机器人可以移动到交叉路口 $4$。无法用 $2$ 日元或更少的花费让机器人到达交叉路口 $4$，因此输出 $3$。

样例说明 2

无论如何重新涂色，都无法让机器人到达交叉路口 $5$。因此，输出 $-1$。

样例说明 3

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

由 ChatGPT 4.1 翻译