#3376. [小云雀]哇咋的骑行(bicycle)

[小云雀]哇咋的骑行(bicycle)

格式

输入格式

从文件 bicycle.in 中读入数据。

第一行三个整数n,m,Sn,m,S,如题目所述 接下来一行nn个非负整数,表示海拔alt[i]alt[i],如题目所述 接下来mm行,每行三个整数(u,v,w)(u,v,w),如题目所述

输出格式

输出到文件 bicycle.out 中。

一行一个整数,如题目所述

样例

5 7 6
1 4 2 2 1
1 2 1
1 3 1
2 3 1
2 4 1
2 5 1
4 5 1
3 4 10
2

数据规范

对于15%的数据,n,m100n,m≤100

对于30%的数据,n,m103n,m≤10^3

对于另外15%的数据,n,m105n,m≤10^5,满足所有的点中,只有两种海拔

对于另外15%的数据,n,m105n,m≤10^5,满足所有的点中,只有三种海拔

对于100%的数据,n,m105n,m≤10^5,满足max(w[i]),max(alt[i]),S1.1109max(w[i]),max(alt[i]),S≤1.1*10^9