题目描述

给定一张 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, L \leq 10^8,0\le c_i\le 10^8$