U2687.心海要回家

数据加强版移步至这里

在提瓦特大陆上，有n个城市或村庄，编号为1 ~ n 。

村庄，城市之间有 m 条双向的通路，连接着两个村庄或城市，从某个村庄或城市到另一个村庄或城市，会遭到愚人众的攻击，进而损失一定的能量。

每次经过一个城市，都会被收取一定的摩拉（包括达马山和珊瑚宫）。路上并没有愚人众~

假设 1 为达马山，n 为珊瑚宫，而她的能量最多为 b，出发时她的能量是满的。如果她的能量降低至负数，则她就无法到达珊瑚宫。

心海不希望花很多钱，肯定不是因为没有摩拉，她想知道，在可以到达珊瑚宫的情况下，她所经过的所有村庄、城市等中最多的一次收取的摩拉的最小值是多少。

第一行三个整数 n , m , b 分别表示 有 n 个村庄或城市，m 条通路，心海的能量为 b 。

接下来有n行，每行1个正整数，f[i]。表示经过城市或村庄i，需要花费 f[i] 元。

再接下来有m行，每行3个正整数，a[i] b[i] c[i]（ 1 <= a[i],b[i] <=n )表示村庄或城市 a[i] 到村庄或城市 b[i] 有一条通路。如果从村庄或城市a[i]到村庄或城市b[i]，或从村庄或城市b[i]到村庄或城市a[i]，需要损失 c[i]点能量。

仅一个整数，表示心海花费最多的一次的最小值。

如果她无法回到珊瑚宫，输出 "你干嘛哈嗨哟"。

对于 100%的数据，满足 1<= c[i] <=1e9，1 <= f[i] <= 1e9，可能有两条边连接着相同的城市。