Problem
今日、エーヌ城では、1 から n までの固有の番号を持つ n 個のパン屋が参加するパイ フェスティバルが開催されます。
いくつかのパン屋は双方向道路でつながっていますが、パン屋 i からパン屋 j まで歩くことができれば、それらの間のルートは 1 つだけです。
En が i 番目のパン屋でパイを食べると、A
i の喜びが得られます。そして番号が v と u のパン屋の間の道を通り過ぎると、パイのおいしい香りが C
v,u の喜びをもたらします。
En さんは、すべてのパン屋に 2 回以上行きたくはありませんが (まったく行かないパン屋もあるかもしれません)、フェスティバルを最大限に活用したいと考えています。
彼はパン屋の 1 つから出発し、既存の道路を使用してパン屋の間のみを横断します。
エンが得ることができる最大の喜びを決定するのを手伝ってください。
入力:
最初の行には、パン屋の数 n (1 <= n <= 50000) と、パン屋間の既存の道路の数 k が含まれています。
2 行目には n 個の数字 A
i (0 <= A
i <= 10000) が含まれています - i 番目のベーカリーでのパイの楽しみ。
次に k 行が続き、それぞれに 3 つの数値 v、u、C (1 <= v, u <= n; v ≠ u; 0 <= C <= 10000) が含まれます。これは、間に道路があることを意味します。ベーカリーは v と u の番号が付けられており、この道の香りは C の喜びをもたらします。
出力:
数字を 1 つ出力してください - 最大限の満足感を得ることができます。
例:
<本体>
| 入力 |
出力 |
2 1
1 1
1 2 1
| 3 |
8 7
1 5 4 6 10 1 2 2
1 2 1
2 3 10
2 4 1
4 5 1
4 6 2
6 7 2
6 8 3
| 37 |
説明:
最初の例では、1 番目のパン屋 (1 お菓子) から始めて、1 番目と 2 番目のパン屋の間の道を歩き (1 お菓子)、2 番目のパン屋 (1 お菓子) を訪れる必要があります。合計の喜び - 1+1+1 = 3.
2番目の例では、5番目のパン屋から始めて（10の楽しみ）、5番目と4番目のパン屋の間の道を歩き（1の楽しみ）、4番目のパン屋を訪れ（6の楽しみ）、4番目と2番目の間の道をたどる必要があります。パン屋(1個)、2個目のパン屋(5個)、2番目と3個目のパン屋の間の道を歩く(10個)、3個目のパン屋(4個)を訪ねる。喜びの合計 - 10+1+6+1+5+10+4 = 37.