Jacek 想要环游世界。不幸的是，他没有太多的钱，因此他希望以尽可能便宜的方式完成这趟旅行。Jacek 发现 Bajtolinii 航空的航班相对便宜，于是他查看了该航空公司的所有航线。他现在正坐在地图前思索。请帮助他！
Jacek 拥有的数据是一份包含 $n$ 个城市的列表，以及一个描述这些城市之间 $m$ 条航线的列表。对于每个城市，Jacek 知道它的经度。每条航线连接两个城市，且支持双向飞行——如果从城市 $a$ 到城市 $b$ 的航班花费 $x$ 个 bajtalar，那么从城市 $b$ 到城市 $a$ 也可以飞行，并且价格相同。
对于每条航线，我们知道执行该航线的飞机是向西飞行还是向东飞行（我们假设没有两个城市具有相同的经度）。每架飞机始终直飞目的地，没有飞越极地，也没有完整地绕地球一圈（即每次飞行跨越的经度小于 360°）。
但这里还存在一个问题：什么叫“环游世界”？Jacek 决定，若一次完整旅程中总共向东飞行的经度数与向西飞行的经度数不同，那么他就认为这是一次环游世界的旅行。他打算从他的家乡城市出发并最终返回。
我们来看几个例子（我们假设所有航线都是合理的，即飞行方向都跨越少于 180 度）：
- 航线：华沙 (21°E) → 莫斯科 (37°E) → 东京 (139°E) → 洛杉矶 (118°W) → 纽约 (73°W) → 华沙 (21°E) 是一次环游世界的旅行（整个旅途中都向东飞行）；
- 航线：华沙 (21°E) → 莫斯科 (37°E) → 东京 (139°E) → 洛杉矶 (118°W) → 迈阿密 (80°W) → 开罗 (31°E) → 都柏林 (6°W) → 华沙 (21°E) 也是一次环游世界的旅行（向东飞行超过 360°，向西只有从开罗到都柏林一段）；
- 航线：华沙 (21°E) → 莫斯科 (37°E) → 新加坡 (103°E) → 洛杉矶 (118°W) → 迈阿密 (80°W) → 开罗 (31°E) → 德里 (77°E) → 悉尼 (151°E) → 布宜诺斯艾利斯 (58°W) → 约翰内斯堡 (28°E) → 华沙 (21°E) 是一次环游世界的旅行（向东飞行超过 720°，向西只有从约翰内斯堡到华沙的一小段）；
- 航线：华沙 (21°E) → 莫斯科 (37°E) → 新加坡 (103°E) → 洛杉矶 (118°W) → 迈阿密 (80°W) → 开罗 (31°E) → 约翰内斯堡 (28°E) → 布宜诺斯艾利斯 (58°W) → 悉尼 (151°E) → 德里 (77°E) → 基辅 (30°E) → 华沙 (21°E) 不是一次环游世界的旅行（向东和向西飞行的经度数恰好相等）。
输入格式
输入的第一行包含两个整数 $n$ 和 $m$（$2 \le n \le 100,000$, $1 \le m \le 200,000$），分别表示 Jacek 地图上的城市数以及 Bajtolinii 航空提供的航线数。城市从 1 到 $n$ 编号。Jacek 将从城市编号为 1 的城市出发。
第二行包含这些城市的经度，表示为一串整数 $w_1, \ldots, w_n$（$0 \le w_i \le 1,296,000$）。数值 $w_i$ 表示城市编号为 $i$ 的城市位于格林威治本初子午线向东 $w_i$ 秒的位置（1 秒 = $1 / 3600$ 度）。任何两个城市的经度不同。
接下来的 $m$ 行，每行描述一条航线。在第 $i$ 行中给出四个整数 $a_i$，$b_i$，$x_i$，$k_i$（$1 \le a_i, b_i \le n$，$a_i \ne b_i$，$1 \le x_i \le 5,000$，$k_i \in {-1, 1}$）。它们表示 Bajtolinii 航空提供从城市 $a_i$ 到城市 $b_i$ 的航班，费用为 $x_i$ 个 bajtalar，并且该航班从 $a_i$ 到 $b_i$ 的方向为东向（若 $k_i = 1$）或西向（若 $k_i = -1$）。返程方向相反。
输出格式
你的程序应输出以城市 1 为起点和终点的最便宜的环游世界旅行所需的费用（以 bajtalar 为单位）。如果不存在这样的旅行，请输出 -1。
示例
输入
5 7 75630 135420 502890 1029600 870750 4 3 1 1 3 2 4 -1 3 5 7 1 1 5 15 1 1 4 10 -1 1 2 2 1 5 4 3 1
输出
23