题目描述

铃有一个 $n$ 个点的无向环，节点编号从 $1$ 到 $n$。边有边权，连接点 $i$ 和点 $i \bmod n + 1$ 的边权值为 $w _ i$。

铃在环内画了 $m$ 条无向边，其中第 $i$ 条边连接节点 $u _ i$ 和 $v _ i$，边权为 $c _ i$。铃不希望破坏环，因此她画出的边不会与环上原有的边重合，也不会使 $u _ i$ = $v _ i$。

为了保证环的美观，铃所画出的边没有在端点外的交叉，也不会重合。

形式化的，对于铃画的任意两条边 ($u _ i$, $v _ i$, $c _ i$) 和 ($u _ j$, $v _ j$, $c _ j$) ($i \neq j$)，不妨设 $u _ i \lt v _ i$ 且 $u _ j \lt v _ j$，则保证以下三者有且仅有一者成立（以下 ($u _ i$, $v _ i$) 和 ($u _ j$, $v _ j$) 为实数域上的两个开区间）

• $(u _ i, v _ i) \cap (u _ j, v _ j) = \varnothing$
• $(u _ i, v _ i) \subset (u _ j, v _ j)$
• $(u _ j, v _ j) \subset (u _ i, v _ i)$ 对于任意两点 $u, v$，铃定义 $dis(u, v)$ 为从 $u$ 到 $v$ 的最短路长度。

现在铃想知道 $\sum \limits _ {i = 1} ^ {n - 1} \sum \limits _ {j = i + 1} ^ n dis(i, j)$ 的值，她把这个问题交给了你。

输入格式

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

第二行 $n$ 个整数，表示 $w _ 1, w _ 2, \cdots, w _ n$。

接下来 $m$ 行，每行三个整数 $u _ i$, $v _ i$, $c _ i$，表示铃画的第 $i$ 条边。

输出格式

一行一个整数，表示 $\sum \limits _ {i = 1} ^ {n - 1} \sum \limits _ {j = i + 1} ^ n dis(i, j)$ 的值。

样例

输入

7 3
7 9 0 6 3 4 7
2 4 8
5 1 6
4 1 2

输出

154

数据范围与提示

对于所有数据，$3\le n \le 2 \times 10^5, 0 \le m \le n - 3, 0 \le w _ {i} \le 10 ^ 3, 0 \le $c _ i$\le 10 ^ 8, 1 \le u _ i, v _ i \le n$。