باشگاه های جدید

پس از کسب جایزه ورزشکار برتر، آقا داوود تصمیم گرفت برای گسترش کارش تعدادی باشگاه جدید دربعضی از شهرهای کشور افتتاح کند. کشور محل سکونت آقا داوود در حال حاضر از $N$ شهر و $N-1$ جاده تشکیل شده است، به طوری که تمام شهرهای کشور به هم متصل‌اند. اما به دلایلی قرار است به زودی یکی از جاده‌های کشور تخریب و کشور به دو بخش افراز شود. همچنین به ازای هر جاده می‌دانیم احتمال تخریب آن وجود دارد یا خیر. آقا داوود می‌داند که تعداد باشگاه‌هایش در دو بخش کشور باید با هم برابر باشند وگرنه تمام محبوبیت خود را بین مردم از دست خواهد داد. حال آقا داوود می‌خواهد تعدادی شهر را برای افتتاح باشگاه انتخاب کند به طوری که با تخریب هر یک از جاده های ممکن، تعداد باشگاه هایش در دو بخش کشور با هم برابر باشند. از طرفی آقا داوود می‌داند افتتاح باشگاه در هر شهر چقدر سود دارد و می‌خواهد بیشترین سود را به دست آورد.

• اول ورودی عدد صحیح $1\leq N \leq 500000$، تعداد شهرها، آمده است.
• در خط دوم ورودی $N$ عدد صحیح $10^{-9} \leq a_1, a_2, \cdots, a_N \leq 10^9$ آمده است که $a_i$ نشان‌دهنده‌ی سود افتتاح باشگاه در شهر $i$ است.
• در $N-1$ خط بعدی، در هر خط سه عدد صحیح $x,y,c$ آمده است که نشان‌دهنده‌ی وجود یک جاده بین شهرهای $x$ و $y$ است . در صورتی که امکان تخریب این جاده وجود داشته باشد، $c = 1$ و در غیر این صورت $c = 0$ خواهد بود ($x \neq y, 1 \leq x, y \leq N, 0 \leq c \leq 1$).
• تضمین می شود در حداقل یکی از جاده ها، $c=1$ است.
• در حداقل از ۳۰ درصد از ورودی‌ها، تعداد جاده های با $c=1$، حداکثر ۵۰ است.

در تنها خط خروجی بیشترین سودی که آقا داوود می‌تواند به دست آورد را چاپ کنید.

• محدودیت زمان: ۲ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

• در مثال اول، حتما جاده اول تخریب می‌شود. آقا داوود شهر ۱ و ۴ را برای افتتاح باشگاه انتخاب می‌کند.
• در مثال دوم، آقا داوود نمی‌تواند باشگاهی افتتاح کند. مثلا اگر شهر ۱ و ۲ انتخاب شود، با تخریب جاده‌ی دوم، آقا داوود محبوبیتش را از دست می‌دهد.
• در مثال سوم آقا داوود در شهرهای ۱، ۳، ۴ و ۶ باشگاه افتتاح می‌کند.

• سوال بعد
• سوال قبل