题目描述

给定一张 $n$ 个点，$m$ 条边的无向图，边有边权，每一个点都有一种颜色 $c_{i}$。

一个友好点对是指一个无序点对其为两个点的颜色差 $\geq L$。

两个点之间的最短路径定义为最小的权值 $d$ 使得存在一条只经过权值 $\leq d$ 的边的路径。

求所有友好点对之间最短路径之和。

输入格式

输入的第一行给出三个数，即上述的 $n, m, L$。

接下来一行有 $n$ 个数，表示每一个点的颜色 $c_i$。

接下来 $m$ 行表示每条边，每行将给出三个数 $u_i, v_i, w_i$，表示点 $u_i$ 和点 $v_i$ 之间有一条长为 $w_i$ 的边。

保证整张图连通。

输出格式

输出一个数，表示所有友好点对之间的最短路径之和。

样例

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

17

数据范围与提示

$1 \leq n \leq 200000$

$1 \leq m \leq 400000$

$1 \leq w_i, c_i \leq 10^8$