题目描述

铃有一个 $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 < v_i$ 且 $u_j < v_j$，则保证以下三者有且仅有一者成立（以下 $(u_i, v_i)$ 和 $(u_j, v_j)$ 为实数域上的两个开区间）：

1. $(u_i, v_i) \cap (u_j, v_j) = \varnothing$
2. $(u_i, v_i) \subset (u_j, v_j)$
3. $(u_j, v_j) \subset (u_i, v_i)$

对于任意两点 $u, v$，铃定义 $\text{dis}(u, v)$ 为从 $u$ 到 $v$ 的最短路长度。

现在铃想知道：

$$\sum_{i = 1}^{n - 1} \sum_{j = i + 1}^n \text{dis}(i, j) $$

的值，她把这个问题交给了你。

---

输入格式

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

第二行 $n$ 个整数，表示 $w_1, w_2, \cdots, w_n$。

接下来 $m$ 行，每行三个整数 $u_i, v_i, c_i$，表示铃画的第 $i$ 条边。

---

输出格式

一行一个整数，表示：

$$\sum_{i = 1}^{n - 1} \sum_{j = i + 1}^n \text{dis}(i, j) $$

的值。

---

样例

输入：

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

输出：

154

---

数据范围与提示

测试点编号	$n \le$	$m$
1~3	300	$= n - 3$
4~6	2000
7~8	$2\times 10^4$	$\le 20$
9~10	$2\times 10^5$	$\le 500$
11~12	$10^4$	$= n - 3$
13~14	$10^5$	$\le n - 3$
15~16		$= n - 3$
17~18	$2\times 10^5$	$\le n - 3$
19~20		$= n - 3$

对于所有数据：

• $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$