题目描述

给定一个 $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$。

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

5 2
1 4 1 2
3 5 1 4

-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

提示

样例 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<B_i \le N$，$1 \le C_i \le M$，$1 \le P_i \le 10^9$，保证图无重边。

说明

翻译自 The 20th Japanese Olympiad in Informatics Final Round D ロボット的英文翻译 Robot。