Ферма и фабрика
Вас приветствует Битоломей, король Байтленда!
Король Битоломей считает, что Бейтленд - довольно уникальная страна. Она довольно маленькая, и все ее граждане (кроме короля) работают либо на ферме, либо на фабрике, расположенных в двух разных городах. Таким образом, каждое утро жители каждого города добираются до этих двух городов в огромных пробках.
Дорожная сеть Байтленда состоит из двунаправленных дорог, соединяющих пары разных городов. Дороги не пересекаются вне городов (однако могут возникнуть тоннели и мосты). Между двумя городами может существовать несколько прямых дорог. Ферма и фабрика доступны из всех городов.
Несколько месяцев назад, пытаясь улучшить ситуацию с дорожным движением, король Битоломей ввел плату за проезд, требуя от граждан платить фиксированную (за каждую дорогу) сумму каждый раз, когда они пользуются дорогой. Битоломей надеялся, что перспектива выплаты денег заставит некоторых граждан пересмотреть свои маршруты и тем самым распределить трафик более равномерно.
Идея короля оказалась, как говорят его советники, не идеальной. Каждый гражданин Байтленда теперь использует самый дешевый маршрут для поездок на работу! Король Битоломей не слишком обеспокоен этим, поскольку доходы от сборов действительно улучшили бюджет королевства. Фактически, средства короля теперь настолько хороши, что он планирует построить себе новую столицу с новым замком в нем. Эта новая столица должна быть соединена с некоторыми другими городами прямыми дорогами, чтобы из нее можно было добраться до любого города. Вновь созданные дороги могут иметь любые неотрицательные дорожные сборы (в частности, дорожные сборы не обязательно должны быть целыми).
Королю Битоломею действительно не нравится шум, производимый машинами, проезжающими мимо его замка. Он хотел бы установить плату за новые дороги, идущие из его новой столицы так, чтобы для любого города 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).