当前没有测试数据。

输入

输入以以下格式从标准输入中给出，所有的输入值都是整数。

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

输出

在标准输出中以一行输出所需的最小金额。如果无论如何涂色都不能使机器人移动到交叉点 $N$，则输出 -1。

Input Example 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

Output Example 1

3

用1元将道路4的颜色从3改为4，用2元将道路6的颜色从4改为2。总共花费3元。

结果是，在交叉点1处的机器人通过指示使用颜色2，可以将机器人移动到交叉点2。然后，通过指示使用颜色4，可以将机器人移动到交叉点4。

无法以2元以下的费用将机器人移动到交叉点4，因此输出3。

Input Example 2

5 2
1 4 1 2
3 5 1 4

Output Example 2

-1

无论如何修改颜色，都无法将机器人移动到交叉点5。因此，输出-1。

Input Example 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

Output Example 3

1

这个输入例子满足小课题2的限制。

Input Example 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

Output Example 4

7