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