- محدودیت زمان: ۱ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
خالهریزه به تازگی یک خانه هزار اتاق خریداری کرده است. این خانه تعداد زیادی اتاق دارد. که مابین هر دو اتاق حداکثر یک در وجود دارد. اما نحوه قرار گرفتن درها طوری است که از هر اتاقی میتوان به اتاق دیگری رفت و هر در شامل تعدادی قفل است. متأسفانه خاله ریزه هنگام تحویل خانه فراموش کرده است کلید اتاقهای خانه را از صاحب قبلی خانه تحویل بگیرد. از طرفی چون برای خرید خانه جدید تمام پولش را خرج کرده است مجبور است در نهایت صرفهجویی تعدادی از درها را انتخاب کرده و برای آنها کلید بسازد طوری که بتواند بین همه اتاقها رفت و آمد کند.
اگر هزینه ساختن کلید برای هر قفل یک دلار باشد شما باید به خاله ریزه کمک کنید و کمترین مقدار پولی که برای تهیه کلیدها لازم است را محاسبه کنید.
ورودی
در خط اول \(1 \leq n \leq 1\ 000\) تعداد اتاق های موجود در خانه خاله ریزه و \(1 \leq m \leq 100\ 000\) تعداد درهای موجود بین این اتاقهاست. سپس در m خط بعدی در هر خط سه عدد w, j, i میآید که مشخص میکند بین اتاق شماره i و اتاق شماره j دری با w قفل وجود دارد.
خروجی
در تنها خط خروجی کمترین میزان هزینه ساختن کلید برای قفلها به طوریکه بتوان بین همه اتاقها رفت و آمد کرد را چاپ کنید.
مثال
ورودی نمونه ۱
3 3
2 1 67
3 1 46
3 2 75
خروجی نمونه ۱
113