Ферма і фабрика
Вас вітає Бітоломей, король Байтленду!
Король Бітоломей вважає, що Байтленд - досить унікальна країна. Вона невелика, і всі її громадяни (окрім короля) працюють або на фермі, або на фабриці, розташованих у двох різних містах. Щоранку жителі кожного міста вирушають до цих двох міст, створюючи величезні затори.
Дорожня мережа Байтленду складається з двонаправлених доріг, що з'єднують пари різних міст. Дороги не перетинаються поза містами (хоча можуть бути тунелі та мости). Між двома містами може існувати кілька прямих доріг. Ферма і фабрика доступні з усіх міст.
Кілька місяців тому, намагаючись покращити ситуацію з дорожнім рухом, король Бітоломей ввів плату за проїзд, вимагаючи від громадян платити фіксовану суму за кожну дорогу щоразу, коли вони нею користуються. Бітоломей сподівався, що перспектива виплати грошей змусить деяких громадян переглянути свої маршрути і таким чином розподілити трафік більш рівномірно.
Ідея короля виявилася, як кажуть його радники, не ідеальною. Кожен громадянин Байтленду тепер використовує найдешевший маршрут для поїздок на роботу! Король Бітоломей не надто стурбований цим, оскільки доходи від зборів дійсно покращили бюджет королівства. Фактично, кошти короля тепер настільки хороші, що він планує побудувати собі нову столицю з новим замком у ній. Ця нова столиця повинна бути з'єднана з деякими іншими містами прямими дорогами, щоб з неї можна було дістатися до будь-якого міста. Новостворені дороги можуть мати будь-які невід'ємні дорожні збори (зокрема, дорожні збори не обов'язково повинні бути цілими).
Королю Бітоломею дійсно не подобається шум, який створюють машини, що проїжджають повз його замок. Він хотів би встановити плату за нові дороги, що йдуть з його нової столиці так, щоб для будь-якого міста v, крім столиці, існували найдешевші шляхи від v до ферми і фабрики, що не проходять через столицю (врахуйте, що v також може бути містом з фермою або фабрикою). З іншого боку, оскільки король не звільнений від мит, він хотів би мінімізувати середню вартість найдешевших шляхів з нової столиці в будь-яке інше місто.
Допоможіть королю визначити мінімально можливу вартість.
Вхідні дані
Перший рядок містить кількість тестів t. Опис тестів наведено нижче:
Кожен тест починається двома цілими числами n, m (2 ≤ n ≤ 10^5, 1 ≤ m ≤ 3 * 10^5), що вказують на кількість міст і кількість доріг у Байтленді. Наступні m рядків описують дороги. Кожна дорога задається трьома цілими числами u, v, c (1 ≤ u, v ≤ n, u ≠ v, 0 ≤ c ≤ 10^6) - індекси двох міст, з'єднаних дорогою, і плата, яку король встановив для цієї дороги. Між будь-якою парою міст може бути кілька доріг.
Індекси міст з фермою і фабрикою рівні відповідно 1 і 2.
Вихідні дані
Для кожного тесту виведіть в окремому рядку мінімально можливу середню вартість проїзду в інші міста з новоствореної столиці. Відповідь виведіть з похибкою не більше 10^(-8).