问题描述

塔子哥是一位热衷旅游的程序员。他所在的国家共有 $n$ 个城市,编号从 $1$ 到 $n$。这些城市之间有 $m$ 条双向的交通线路,分别为飞机线路和火车线路。塔子哥起始位于编号为 $1$ 的城市,他计划前往编号为 $n$ 的城市进行旅游。

在这个国家,每个城市都有一个固定的时间 $a_i$,表示在该城市中转换交通工具所需的时间。特别地,在出发城市 $1$ 和目的地城市 $n$,塔子哥不需要转换交通工具。

塔子哥可以自由选择乘坐飞机或火车前往下一个城市。他希望能够以最短的时间从出发城市抵达目的地城市。

输入格式

第一行包含两个正整数 $n$ 和 $m$,分别表示城市数量和交通线路数量。

第二行包含 $n$ 个正整数 $a_1, a_2, \ldots, a_n$,表示每个城市中转换交通工具所需的时间。

接下来 $m$ 行,每行包含四个正整数 $u, v, w, t$,其中 $u$ 和 $v$ 表示线路连接的两个城市编号, $w$ 表示沿该线路行驶所需的时间, $t$ 的值为 $1$ 表示该线路为飞机线路,值为 $2$ 表示该线路为火车线路。

$1\leq n,m \leq 10^5$

$0\leq a_i\leq 10^9$

$1\leq u,v\leq n, 1\leq w\leq 10^9, 1\leq t\leq 2$

输出格式

输出一个整数,表示塔子哥从出发城市到达目的地城市所需的最短时间。

样例输入

3 3
1 1 1 
1 2 1 1
2 3 1 2
2 3 1 2

样例输出

3

样例解释

塔子哥可以按照以下路线行进:

1. 从城市 $1$ 乘坐飞机前往城市 $2$,耗时 $1$ 个单位时间。
2. 在城市 $2$ 中转换交通工具,耗时 $1$ 个单位时间。
3. 从城市 $2$ 乘坐火车前往城市 $3$,耗时 $1$ 个单位时间。

总共耗时 $3$ 个单位时间,无法再缩短时间。

评测数据与规模

对于所有评测用例,满足 $1 \leq n, m \leq 10^5, 0 \leq a_i \leq 10^9, 1 \leq u, v \leq n, w \in \{1, 2\}, 1 \leq w \leq 10^9$。保证任意两个城市之间是连通的。