j01005. 限费通行 未做

有 $n$ 座城市，第 $i$ 座的过路费为 $c_i$（经过就要付，起点和终点也要付）。有 $m$ 条双向道路，第 $i$ 条的油耗为 $d_i$。油箱容量为 $B$，出发时满油、途中不加油。求能从 $1$ 号城开到 $n$ 号城时，「经过城市的过路费最大值」的最小值；若不可达输出 $-1$。

第一行三个整数 $n,m,B$；第二行 $n$ 个整数 $c_i$；接下来 $m$ 行，每行三个整数 $u,v,d$。

一行一个整数：最小的最大过路费，或 $-1$。

• $2\le n,m\le 2\times 10^5$
• $1\le B,c_i,d_i\le 10^9$，$1\le u,v\le n$