### 问题描述

从所周知，小秋特别喜欢旅行。

小秋所在的国家可以看成一个 $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$。

注：图中可能会有重边和自环。