Migrated from Lutece 2710 土豆的图

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

众所周知，$lotato$ 有一张 $n$ 个点，$m$ 条边的带权无向图。第 $i$ 个点的颜色为 $c_i$。

$d(s, t)$ 表示从点 $s$ 到点 $t$ 的权值最小的路径的权值。

请注意，在本问题中 $lotato$ 定义一条路径的权值为路径上权值最大的边的权值。

现在 $lotato$ 想求所有满足 $u < v$, $|c_u -c_v| \geq L$ 的点对 $(u, v)$ 的 $d(u, v)$ 之和。

Input

第一行，三个整数 $n, m, L$ ，表示点数，边数和参数 $L$ 。

第二行，$n$ 个整数，第 $i$ 个数为第 $i$ 个点的颜色 $c_i$ 。接下来 $m$ 行，每行三个整数 $u_i$ $v_i$ $w_i$，描述了一条边。

Output

共一行，一个整数，表示答案。

Samples

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

17

Constraints

$1 \leq n \leq 2×10^5，1 \leq m \leq 5×10^5，0 \leq c_i , L \leq 10^9，1 \leq u, v \leq n，0 \leq w \leq 10^8$

图保证联通

Note

注意：可能会有重边和自环

Resources

2022 UESTC ICPC Training for Graph