T2

题目描述

有 $n$ 个城市，编号为 $1 \cdots n$ ，共有 $m$ 条双向公路。汽车驶过这条公路需要支付 $w_i$ 的费用，公路旁设有风景区，好看度为 $b_i$ 。

现汽车要从 $1$ 号城市前往 $n$ 号城市，行驶过程中可以免去所选路径中好看度最高的一条公路的费用（若路径中有多条好看度同为最高的公路，也仅能免去一次费用），请求出总费用的最小值。

注意：若无法从 $1$ 号城市到达 $n$ 号城市，请输出 -1。

第一行两个整数 $n, m$ ，分别表示城市的数量和公路的数量。

接下来 $m$ 行，每行四个整数 $u, v, w_i, b_i$ ，表示一条连接 $u$ 号城市与 $v$ 号城市的双向公路，驶过该公路的费用为 $w_i$ ，公路旁风景区的好看度为 $b_i$ 。

输出一行一个整数，表示从 $1$ 号城市前往 $n$ 号城市的最小总费用。若无法到达，输出 -1。

对于所有测试数据，满足：