یک گروه موسیقی ناشناخته‌ می‌خواهد برای کسب شهرت در همه‌ی شهر‌های کشور خود کنسرت‌ برگزار کند. مانند خیلی از کشور‌ها ساختار جاده‌های این کشور نیز یک گراف درخت می‌باشد و شهر‌ها از ‎$1$‎ تا ‎$n$‎ شماره‌گذاری شده‌اند. به این معنی که شهر‌های این کشور با تعدادی جاده‌ی دو طرفه به هم متصل شده‌اند به گونه‌ای که مسیر بین هر دو شهر یکتا می‌باشد. با توجه به هزینه‌های سفر و اشتیاق اعضای گروه برای ثروتمند شدن، تصمیم گروه بر آن شده است که در انتهای سفر‌شان بیش‌ترین سود ممکن را به دست آورند.

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

گروه موسیقی سفر خود را از یک شهر دلخواه آغاز می‌کند و با اجرای کنسرت در شهر آغازین مقداری پول برای ادامه‌ی سفر خود به دست می‌آورد. گروه به همه شهرها سفر می‌کند و در نهایت به شهر اولیه‌ی خود باز می‌گردد. برای عبور از یک جاده گروه باید به اندازه‌ی هزینه‌ی سفر در آن جاده پول داشته باشد، به این معنا که در طول سفر هیچ گاه نباید خرج گروه از دخلش بیش‌تر شود. به گروه کمک کنید و حساب کنید که بیش‌ترین سودی که می‌توان با انجام این برنامه به‌دست آورد چه‌قدر می‌باشد‎. ‎

• در خط اول ورودی عدد ‎$n$‎، نشان دهنده‌ی تعداد شهر‌های کشور را بخوانید.
• سپس در خط دوم ‎$n$‎ عدد بخوانید که عدد ‎$i$‎ام نشان دهنده‌ی ‎$C_i$‎ می‌باشد.
• سپس در ‎$n-1$‎ خط بعدی در هر خط شماره‌ی شهر شروع و پایان یک جاده و هزینه‌ی هربار عبور از آن جاده را بخوانید.
• ‎ $1 \leq n \leq 2\times 10^5$‎.
• تمامی اعداد ورودی صحیح و مثبت هستند و از ‎$10^9$‎ بیشتر نمی‌باشند.
• تضمین می‌شود که ساختار گراف ورودی یک درخت می‌باشد.

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

‎

• زیرمسئله‌ی اول (۱۵ نمره): در همه‌ی تست‌ها ‎$n\leq 20$‎.
• زیرمسئله‌ی دوم (۲۰ نمره): در همه‌ی تست‌ها ‎$n\leq 2000$‎ و درخت ورودی مسیر است.
• زیرمسئله‌ی سوم (۲۰ نمره): در همه‌ی تست‌ها ‎$n\leq 2000$‎.
• زیرمسئله‌ی چهارم (۴۵ نمره): در همه‌ی تست‌ها ‎$n\leq 2\times 10^5$‎.

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

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