题目描述

一个物流网络由 $n$ 个城市和 $m$ 条双向公路组成。每条公路有运输费用 $w$ 和景观评分 $b$。

运输车从城市 $1$ 到城市 $n$ 时，需支付经过公路的运输费用之和。优惠政策：可以免除路径上景观评分最高的那条公路的费用（如有并列最高，只免一条）。

求从城市 $1$ 到城市 $n$ 的最小运输费用。如果无法到达，输出 $-1$。

输入格式

第一行两个整数 $n, m$。

接下来 $m$ 行，每行 $u, v, w, b$，表示城市 $u$ 和 $v$ 之间有一条双向公路，费用 $w$，景观评分 $b$。

输出格式

输出一个整数，表示最小运输费用。如果无法到达，输出 $-1$。

样例输入

3 3
1 2 10 5
2 3 20 6
1 3 100 1

样例输出

0

数据范围

$1 \le n \le 5000$，$1 \le m \le 5000$，$1 \le w, b \le 10^9$。