#6493. graph

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

题目描述

给定一张 nnn 个点,mmm 条边的无向图,边有边权,每一个点都有一种颜色 cic_{i}ci

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

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

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

输入格式

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

接下来一行有 nnn 个数,表示每一个点的颜色 cic_ici

接下来 mmm 行表示每条边,每行将给出三个数 ui,vi,wiu_i, v_i, w_iui,vi,wi,表示点 uiu_iui 和点 viv_ivi 之间有一条长为 wiw_iwi 的边。

保证整张图连通。

输出格式

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

样例

样例输入
4 5 2
6 4 5 2
1 2 8
2 3 7
2 4 8
1 3 2
1 4 1
样例输出
17

数据范围与提示

1≤n≤2000001 \leq n \leq 2000001n200000

1≤m≤4000001 \leq m \leq 4000001m400000

1≤wi,ci≤1081 \leq w_i, c_i \leq 10^81wi,ci108