Темні дороги#6224
Економічні часи зараз важкі, навіть у Байтлендії. Щоб зменшити експлуатаційні витрати, уряд Байтлендії вирішив оптимізувати освітлення доріг. До цього часу кожна дорога була освітлена всю ніч, що коштує 1 байтлендійський долар за метр на день. Щоб заощадити гроші, вони вирішили більше не освітлювати кожну дорогу, а вимикати освітлення деяких вулиць. Щоб жителі Байтлендії все ще почувалися в безпеці, вони хочуть оптимізувати освітлення таким чином, щоб після затемнення деяких вулиць вночі все ще залишався принаймні один освітлений шлях від кожного перехрестя в Байтлендії до кожного іншого перехрестя.
Яка максимальна щоденна сума грошей, яку уряд Байтлендії може заощадити, не змушуючи своїх жителів почуватися в небезпеці?
Вхідний файл містить кілька тестових випадків. Кожен тестовий випадок починається з двох чисел і , які представляють кількість перехресть у Байтлендії та кількість доріг відповідно. Вхід завершується m = n = 0. В іншому випадку, 1 \le m \le 200000 і m-1 \le n \le 200000. Далі йдуть трійок цілих чисел , , , що вказують на двосторонню дорогу між і довжиною метрів (0 \le x, y < m і x \ne y). Граф, заданий кожним тестовим випадком, є зв'язним.
Загальна довжина всіх доріг у кожному тестовому випадку менша за 2^{31}.
Для кожного тестового випадку виведіть один рядок, що містить максимальну щоденну суму, яку уряд може заощадити.
Приклад 1