Roads

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

• در سطر اول ورودی به ترتیب دو عدد طبیعی ‎$n$‎، تعداد‌ راس‌های گراف و ‎$e$‎، تعداد یال‌های آن آمده است.
• هر یک از ‎$e$‎ سطر بعدی، به ترتیب شامل سه عدد طبیعی ‎$u$‎، ‎$v$‎ و ‎$w$‎ است که نشانگر یک یال از ‎$u$‎‌ به ‎$v$‎ با وزن ‎$w$‎ می‌باشد.
• تضمین می‌شود که گراف داده شده در ورودی همبند است و گراف یال چندگانه و طوقه ندارد. همچنین تضمین می‌شود هر یال درون حداقل یک دور می‌باشد.
• $2 \leq n \leq e \leq 10^5$‎.
• $1 \leq u,v \leq n‎, ‎u \ne v$‎.
• ‎ $1 \leq w \leq 10^9$‎.

در تنها سطر خروجی پاسخ مسئله را چاپ کنید. دقت کنید که این مقدار ممکن است از ‎$2^{32}$‎ بیشتر شود.

• زیرمسئله‌ی اول (۱۰ نمره): در همه‌ی تست‌ها ‎$n,e\leq 10^3$‎.
• زیرمسئله‌ی دوم (۳۰ نمره): در همه‌ی تست‌ها ‎$n\leq 10^3$‎ و ‎$e\leq 10^5$‎.
• زیرمسئله‌ی سوم (۵۵ نمره): در همه‌ی تست‌ها ‎$n,e\leq 10^5$‎.
• زیرمساله‌ی چهارم (۵ نمره): در همه‌ی تست‌ها ‎$n,e\leq 10^6$‎.

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

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

‎