题目背景

相聚的时候，总是很短；期待的时候，总是很长。 —— 汪国真

Minecraft 红石数电爱好者 $xty$ 在看到脏小豆骗赞服的编码全物品后大受震撼，下定决心要学习先进知识，也要造一个编码全物品。但是由于设计上的缺陷，导致编码全物品在连续分类大量物品时容易误判满仓而导致降频。$xty$ 对此很苦恼，因为他对机器的效率有着极致的追求，而降频显然会极大地影响机器效率。因此，他想为编码全物品设计一个规划运算模块，通过算法计算减少这种情况的发生。所以 $xty$ 找到了一位神犇 —— 你，请你帮他设计规划运算模块的程序。

由于全物品需要尽快得到结果，以便开始分类，没有很多的时间等待程序计算完成，所以你只有 $1000$ $ms$ 的时间。

Tips：

传统全物品就是简单的物品分类单片的堆叠，通过物流水道依次通过每一个分类单片，时间复杂度为 $O(n)$。

编码全物品通过对每一个物品进行编码，当物品被投入全物品时，识别物品的编码，直接发往对应的箱子，时间复杂度大大降低。具体时间复杂度视实际情况而定。

题目描述

编码全物品共有 $n$ 个节点，每个节点的编号分别为 $1,2,\cdots ,n$，其中投料口的节点编号为 $1$。节点之间由一些物流水道相连接（众所周知，水只能单向流动，所以物流水道是有向的），共有 $m$ 条物流水道，每条水道从节点 $u$ 流向节点 $v$，通过该水道正常耗时为 $w$。同时，编号为 $i$ 的节点有一个堵塞系数 $h_{i}$，每条水道都有一个敏感系数 $k$。物品通过一条水道的实际耗时为 $w+k\cdot s$（$s$ 是在物品运输路径中，所有早于当前节点 $u$ 流经节点的里，$h_{i}$ 严格高于 $h_{v}$ 的节点个数）。

编码全物品的规划运算模块会计算从投料口到达每一个节点所需的最短时间，但由于游戏限制，无法很精确地模拟物品实际通过的路径，所以为了简便运算，规划运算模块会将其计算过程中已经确定最短路径的节点作为已经过节点进行计算。

现在有一个物品被投入投料口，该物品对应箱子的节点编号恰好为 $n$。请你输出规划运算模块计算出的物品完成分类所需最短时间。

规划运算模块的计算过程：在所有没有确定最短路长度的节点中，选取一个目前已知路径长度最小的结点，先计算出它的最短路，把这个计算结果确定为它的最短路。此过程循环进行，直到所有节点均已被确定最短路长度。

输入格式

输入第 $1$ 行有 $2$ 个整数 $n$ 和 $m$，表示有 $n$ 个节点和 $m$ 条水道。

输入第 $2$ 行有 $n$ 个整数，第 $i$ 个整数表示编号为 $i$ 的节点的堵塞系数 $h_{i}$。

接下来 $m$ 行，每行有 $4$ 个整数 $u,v,w,k$，表示有一条水道，起点编号为 $u$，终点编号为 $v$，正常耗时为 $w$，敏感系数为 $k$。

输出格式

输出共 $1$ 行 $1$ 个整数，表示规划运算模块计算出的物品完成分类所需的最短时间。若发现无法到达对应箱子，则输出 $-1$。

样例

5 7
7 6 3 2 9
1 3 40 72
2 5 45 54
2 3 40 61
3 4 87 49
4 2 7 82
4 1 78 22
4 5 30 91

327

11 13
14 1 12 2 6 10 5 3 16 11 20
1 7 100 60
1 2 67 27
2 3 94 25
2 10 79 99
3 7 58 36
3 5 2 3
3 6 15 13
4 8 33 20
5 10 38 35
8 9 86 20
9 6 24 85
10 6 83 12
11 9 62 69

-1

见 样例.zip\text3.in

见 样例.zip\text3.out

说明 / 提示

数据规模与约定

对于 $20\%$ 的数据，满足 $n\in\left[2,1000 \right ],m\in \left [ 1,2000 \right ]$。

对于 $50\%$ 的数据，满足 $n\in \left [ 2,10000 \right ],m\in \left [ 1,20000 \right ]$。

对于 $100\%$ 的数据，满足 $n\in \left [ 2,100000 \right ],m\in \left [ 1,200000 \right ],1\le u\le n,1\le v\le n,w\in \left [ 1,1000000 \right ],k\in \left [ 0,1000000 \right ],h_{i} \in \left [ 1,2^{30} \right )$，保证 $h_{i}$ 互不相同。

特别的： 对于 $100\%$ 的数据，保证使用不同的图的遍历顺序时，程序输出相同。

样例文件