格式

输入格式

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

第一行三个整数$n,m,S$，如题目所述 接下来一行$n$个非负整数，表示海拔$alt[i]$，如题目所述 接下来$m$行，每行三个整数$(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,m≤100$

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

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

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

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