### 问题描述 从所周知，小秋特别喜欢旅行。 小秋所在的国家可以看成一个 $n$ 个点 $m$ 条边的无向图。 小秋所在的节点编号为 $1$，现在他想要去编号为 $n$ 的城市旅游，但是经费有限，去 $n$ 号城市的路费之和不能超过 $k$。 由于每个城市只有一个中转车站，因此每个城市都有一个固定的中转时间（包括起点）。换句话说，在第 $i$ 个城市前往其他城市，中转时间为 $t_i$，终点不需要中转。 由于小秋不喜欢在旅游的过程中等车太久，他希望在路费不超过 $k$ 的情况下，路径上中转时间最长的那个城市的中转时间尽可能小。你只需要求出这个最大中转时间的最小值。 ### 输入格式 第 $1$ 行输入包含 $3$ 个整数 $n,m,k$，分别表示无向图的点数，边数和最大路费和。 第 $2$ 行输入包含 $n$ 个整数，第 $i$ 个整数代表第 $i$ 个城市的中转时间。 接下来 $m$ 行，每行输入 $3$ 个整数 $a ,b ,c$，表示无向图的边的两个顶点和经过这条边所需要的路费。 ### 输出格式 输出仅一行，一个整数，表示最大中转时间的最小值。 ### 样例输入 ``` 6 7 11 4 3 4 4 5 20 1 2 3 2 3 4 2 4 7 2 5 3 4 6 1 1 5 2 5 6 8 ``` ### 样例输出 ``` 4 ``` ### 说明 从 $1$ 到 $6$ 的路径并且路费小于等于 $11$ 的有 $2$ 条； 路径一：$1 \rightarrow 5 \rightarrow 6$，路费之和为 $10$，最大中转时间为 $5$； 路径二：$1 \rightarrow 2 \rightarrow 4 \rightarrow 6$，路费之和为 $11$，最大中转时间为 $4$。 ### 评测数据规模 对于 $20$% 的评测数据，$1 \leq n , m \leq 10^3$； 对于 $100$% 的评测数据，$1 \leq n ,m \leq 10^5 , 1 \leq t_i,k,c \leq 10^9$。 注：图中可能会有重边和自环。