#6493. graph

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Dance_Of_Faith

题目描述

给定一张 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