Problem Statement

高橋君が住む国には $N$ 箇所の町と町同士をつなぐ一方通行の道が $M$ 本あり、それぞれの町には $1$ から $N$ の番号が割りふられています。 $i$ 番目の道は $a_i$ 番の町から $b_i$ 番の町へ移動することが可能であり、移動に $c_i$ 分だけかかります。

所持金が $0$ 円の高橋君は $T$ 分間のトレジャーハントに出かけることにしました。高橋君は開始 $0$ 分の時点で $1$ 番の町にいます。また、開始から $T$ 分の時点にも $1$ 番の町にいなくてはなりません。高橋君が $i$ 番の町に $1$ 分間滞在すると、 $A_i$ 円が高橋君の所持金に加算されます。

$T$ 分間のトレジャーハントによって高橋君の所持金は最大いくらになるか求めてください。

Input

入力は以下の形式で標準入力から与えられる。

N M T
A_1 … A_N
a_1 b_1 c_1
.
.
.
a_M b_M c_M

• $1$ 行目に町の数と道の数、トレジャーハントの分数を表す $3$ つの整数 $N,M,T (2≦N≦10^5, 1≦M≦min(N(N-1),10^5), 1≦T≦10^9)$ が空白区切りで与えられる。
• $2$ 行目には $i$ 番目の町に滞在したときに得られるお金の情報を表す整数 $A_i(1≦A_i≦10^5)$ が空白区切りで与えられる。
• $3$ 行目から続く $M$ 行のうち $i$ 行目においては、 $i$ 番目の道の情報を表す $3$ つの整数 $a_i, b_i, c_i (1≦a_i,b_i≦N,a_i≠b_i, 1≦c_i≦10^5)$が空白区切りで与えられる。
• $i≠j$ であるような $i,j$ において、$a_i≠a_j$ または $b_i≠b_j$ のどちらかが成立する。

Output

トレジャーハントの結果としてありうる高橋君の所持金のうち最大値を $1$ 行に出力せよ。改行を忘れないこと。

部分点

この問題には部分点が設定されている。

• $1≦N≦200$ を満たすデータセットに正解した場合 $50$ 点が与えられる。
• 追加制約のないデータセットに正解した場合は、追加で $50$ 点が与えられ、合計 $100$ 点が得られる。