Одна маггловская фирма предложила Люциусу Малфою заключить контракт на прокладку сети портшлюзов между филиалами фирмы. Магглы наивно полагают, что себестоимость портшлюза зависит от расстояния, на которое тот переносит, и готовы заплатить за каждый метр проложенной сети. Единственное их требование — чтобы с помощью этих портшлюзов можно было добраться от каждого филиала к каждому, и чтобы не было лишних портшлюзов (то есть, чтобы не существовало портшлюзов, которые можно было бы убрать с сохранением условия связности всех филиалов).

Люциус понимает, что себестоимость портшлюза определяют совсем другие факторы. Он хочет надуть магглов и сделать такой проект сети, при котором отношение суммарной себестоимости портшлюзов к той сумме, которую заплатят магглы, оказалось бы минимальным. Таким образом, он стремится минимизировать среднюю себестоимость одного метра сети. Помогите Люциусу надуть магглов.

В первой строке входа находится число N (1 ≤ N ≤ 1000) — количество филиалов. Во второй строке находится число M (1 ≤ M ≤ 500000) — количество пар филиалов, между которыми технически возможно создать портшлюз. В следующих M строках идет описание каждой пары: через пробел выписаны номера филиалов, которые можно соединить, расстояние между ними в метрах, и себестоимость прокладки портшлюза. Себестоимость и расстояние — целые числа от 1 до 10⁶. Можно считать, что какую-то сеть портшлюзов, удовлетворяющую условиям заказчика, всегда можно построить. Для любой пары филиалов есть не более одного способа соединения. По условиям контракта нельзя соединять филиал с самим собой.

Вывести минимальную среднюю стоимость одного метра сети с точностью до 10⁻⁸. Средняя стоимость одного метра равна отношению суммарной себестоимости к суммарной длине сети.