در جست‌وجوی یار


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

به لبو خبر رسیده که یار کادوهای لبو را گرفته و فِلِنگ را بسته‌‌است. (البته هنوز از کشور خارج نشده‌است.)

کشور لبواینا nn شهر دارد و بین بعضی از شهرهای آن جادّه‌ی دوطرفه وجود دارد.

در این کشور برای عبور از هر جادّه‌‌ تعدادی مجوز نیاز است. اگر طول جادّه‌ای ll باشد و در نمایش دودویی عدد ll، رقم مربوط به 2i2^i برابر 11 باشد، برای عبور از این جادّه داشتن مجوز نوع ii الزامی است. بهای مجوز نوع ii برابر 2i2^i تومان است. اگر لبو مجوز نوع ii را خریداری کند، برای عبور از هرجادّه‌ای می‌تواند از آن مجوز استفاده کند.

از آنجا که لبو نمی‌داند یار به کدام شهر رفته‌است‌، حدّاقل بهایی که باید برای تهیّه‌ی مجوز بپردازد تا مطمئن باشد می‌تواند یار را پیدا کند چند تومان است؟

ورودی🔗

در خط اوّل ورودی دو عدد nn و mm، تعداد شهرهای کشور لبواینا و تعداد جادّ‌ه‌‌های کشور، آمده است.

درmm خط بعد در هر خط سه عدد uiu_i و viv_i و wiw_i آمده‌است که مشخصّات جادّه‌ی ii اُم هستند. به این معنی که یک جادّه‌ی دوطرفه به طول wiw_i بین شهر uiu_i و viv_i وجود دارد.

تضمین می‌شود بین هر دو شهر حداکثر یک جادّه وجود دارد و از هر شهری به هر شهر دیگر حداقل یک مسیر موجود است.

1n,m5×1051 \leq n,m \leq {5 \times{}10^5} 1uivin1 \leq u_i \ne v_i \leq n 1wi1091 \leq w_i \leq 10^9

خروجی🔗

در خروجی یک عدد چاپ کنید که برابر حداقل بهایی است که لبو باید بپردازد تا از پیدا کردن یار مطمئن شود.

مثال🔗

ورودی نمونه ۱🔗

3 3
1 2 4
2 3 2
3 1 1
Plain text

خروجی نمونه ۱🔗

3
Plain text

توضیح تمونه ۱: کافی است لبو مجوز‌های نوع 00 و نوع 11 را خریداری کند.

ورودی نمونه ۲🔗

4 4
1 2 5
2 3 2
3 4 2
4 1 4
Plain text

خروجی نمونه ۲🔗

6
Plain text
ارسال پاسخ برای این سؤال
در حال حاضر شما دسترسی ندارید.