Problem
امروزه، قلعه Aisne میزبان جشنواره پای است که در آن n نانوایی شرکت می کنند که هر یک از 1 تا n عدد منحصر به فرد خود را دارند.
برخی از نانوایی ها با جاده های دو طرفه به هم متصل می شوند، اما به گونه ای که اگر بتوان از نانوایی i تا نانوایی j را پیاده طی کرد، دقیقاً یک مسیر بین آنها وجود دارد.
وقتی ان در نانوایی i-th پای می خورد، لذت A
i می برد. و اگر در امتداد جاده بین چند نانوایی با شماره های v و u رد شود، عطر خوشمزه پای ها لذت C
v,u را به ارمغان می آورد.
اِن نمی‌خواهد بیش از یک بار به هر نانوایی برود (بعضی‌ها ممکن است اصلاً نروند)، اما می‌خواهد بیشترین بهره را از جشنواره ببرد.
او از یکی از نانوایی ها شروع می کند و فقط با استفاده از جاده های موجود از بین آنها عبور می کند.
به En کمک کنید تا حداکثر لذت ممکنی را که می تواند بدست آورد تعیین کند.
ورودی:
خط اول شامل عدد n (1 <= n <= 50000) - تعداد نانوایی‌ها و عدد k - تعداد جاده‌های موجود بین نانوایی‌ها است.
خط دوم حاوی 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 را به ارمغان می آورد.
خروجی:
چاپ یک عدد - حداکثر رضایت ممکن.
مثال:
<بدن>
| ورودی |
خروجی |
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 خوراکی) بازدید کنید. لذت کلی - 1+1+1 = 3.
در مثال دوم، شما باید از نانوایی 5 شروع کنید (10 لذت)، در امتداد جاده بین نانوایی 5 و 4 (1 لذت) قدم بزنید، از نانوایی چهارم (6 لذت) بازدید کنید، جاده بین 4 و 2 را دنبال کنید. نانوایی (1 غذا)، بازدید از نانوایی دوم (5 غذا)، پیاده روی در امتداد جاده بین نانوایی دوم و سوم (10 خوراک)، از نانوایی سوم (4 غذا). لذت کل - 10+1+6+1+5+10+4 = 37.