P7407 [JOI 2021 Final] 机器人 / Robot

给定一个 $N$ 点无向图，这 $N$ 个点编号为 $1 \sim N$，由 $M$ 条边连接，这 $M$ 条边编号为 $1 \sim M$，分别连接点 $A_i$ 与点 $B_i$。这 $M$ 条边染上了颜色，第 $i$ 条边的颜色为 $C_i$，保证 $C_i \in [1,M]$ 但不保证 $C_i$ 互不相等。 你很智能，如果我说一种颜色 $L$，满足下面这些要求的话： - 存在一条边的颜色为 $L$ 且一个端点为你现在在的点。 - 不存在大于等于两条边满足颜色为 $L$ 且一个端点为你现在在的点。 你就会移动到这条边走向对面的端点，否则你就会原地不动。 你现在在点 $1$ 处，我要你移动到点 $N$ 处，我可以告诉你一些颜色你按照这些颜色走。但这个图有可能不满足能从 $1$ 走向 $N$ 这个条件，因此我要改变一些边的颜色。改变第 $i$ 条边的颜色使其变为另一个在区间 $[1,M]$ 里的数需要的代价为 $P_i$，我想问，至少需要多少代价才能让你成功移动到点 $N$？

第一行两个整数 $N,M$ 代表无向图点数和边数。 接下来 $M$ 行每行四个整数 $A_i,B_i,C_i,P_i$ 描述一条边。

一行一个整数代表最小代价，如果无法到达输出 $-1$。

#### 样例 1 解释 我可以进行如下操作： - 将第 $4$ 条边的颜色改为 $4$，代价 $1$。 - 将第 $6$ 条边的颜色改为 $2$，代价 $2$。 总代价 $3$，然后我如下使唤你： - 我说“颜色 $2$！”你从点 $1$ 移动到点 $2$。 - 我说“颜色 $4$！”你从点 $2$ 移动到点 $4$。 #### 样例 2 解释 很遗憾，即使如此智能的你也到达不了第 $N$ 个点。 #### 数据规模与约定 **本题采用捆绑测试。** - Subtask 1（34 pts）：$N \le 1000$，$M \le 2000$。 - Subtask 2（24 pts）：$P_i=1$。 - Subtask 3（42 pts）：无特殊限制。 对于 $100\%$ 的数据，$2 \le N \le 10^5$，$1 \le M \le 2 \times 10^5$，$1 \le A_i