G: トレジャーハンター (Treasure Hunter)

財宝の山が N 個あり、それぞれの山は 1 から N までで番号づけられている。i 番目の山には価値 p_i のお宝が眠っており、このお宝はその山に訪れた時点で得ることができる。一度お宝を得るとその山からはお宝がなくなってしまうので、お宝はそれぞれ一度しか得ることはできない。

異なる山に移動するには必ず道を利用しなければならない。山と山の間には合計 N-1 本の道があり、i 番目の道は山 u_i と v_i を双方向に結んでいる。もしもどの道も問題なく通行可能であると仮定すると、任意の 2 つの山について相互に行き来可能であることが分かっている。

どの道も長らく誰も通行しておらず修復しないと渡れないため、i 番目の道について最初に渡る際には c_i 円を支払って工事し、通行可能にする必要がある。一度工事した道であればそれ以上お金を支払うことなく通行が可能である。

トレジャーハンターであるあなたは、道の工事費用の予算を W 円持っている。あなたの目的は、はじめに降り立つ山を任意に 1 つ決め、合計 W 円以下で道を工事して異なる山に移動することで、得られるお宝の価値の合計を最大化することである。あなたは最大でどれだけの価値を得られるだろうか？

なお、お宝を途中で換金することはできないため、お宝を工事費用として使用することはできないことに注意せよ。

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

N W
p_1 p_2 ... p_N
u_1 v_1 c_1
:
u_{N-1} v_{N-1} c_{N-1}

1 行目では、山の数 N と工事費用の予算 W が与えられる。
2 行目では、i 番目の山に眠っているお宝の価値 p_i が与えられる。
3 行目から N+1 行目では、道の情報が与えられる。2+i 行目は i 番目の道の情報を表しており、山 u_i と v_i の間に工事費用 c_i の道があることを表す。

得られるお宝の価値の合計の最大値を 1 行に出力せよ。末尾の改行を忘れないこと。

山 1 または山 2 に降り立ち、山 1 と山 2 を結ぶ道を工事し、山 1 と山 2 にあるお宝を得るのが最適である。工事費用の予算は 10 であるので、ふたつの道を両方とも工事することはできない。