Одна маггловская фирма предложила Люциусу Малфою заключить контракт на
прокладку сети портшлюзов между филиалами фирмы. Магглы наивно полагают, что
себестоимость портшлюза зависит от расстояния, на которое тот переносит, и
готовы заплатить за каждый метр проложенной сети.
Единственное их требование — чтобы с помощью этих портшлюзов можно было
добраться от каждого филиала к каждому, и чтобы не было лишних портшлюзов (то
есть, чтобы не существовало портшлюзов, которые можно было бы убрать
с сохранением условия связности всех филиалов).
Люциус понимает, что себестоимость портшлюза определяют совсем другие факторы.
Он хочет надуть магглов и сделать такой проект сети, при
котором отношение суммарной себестоимости портшлюзов к той сумме,
которую заплатят магглы, оказалось бы минимальным. Таким образом, он
стремится минимизировать среднюю себестоимость одного метра сети.
Помогите Люциусу надуть магглов.
Исходные данные
В первой строке входа находится число N (1 ≤ N ≤ 1000) — количество филиалов. Во второй строке находится число M (1 ≤ M ≤ 500000) — количество пар филиалов, между которыми
технически возможно создать портшлюз. В следующих M строках идет описание
каждой пары: через пробел выписаны номера филиалов, которые можно соединить,
расстояние между ними в метрах, и себестоимость прокладки портшлюза.
Себестоимость и расстояние — целые числа от 1 до 106. Можно
считать, что какую-то сеть портшлюзов, удовлетворяющую условиям заказчика,
всегда можно построить. Для любой пары филиалов есть не более одного способа соединения.
По условиям контракта нельзя соединять филиал с самим собой.
Результат
Вывести минимальную среднюю стоимость одного метра сети с точностью до 10−8. Средняя стоимость одного метра равна отношению суммарной себестоимости к суммарной длине сети.
Примеры
исходные данные | результат |
---|
3
3
1 2 50 60
1 3 100 100
2 3 100 100
| 1
|
3
3
1 2 1000 3000
1 3 1 5
2 3 1000 1997
| 2
|
Автор задачи: Автор — Ден Расковалов, текст — Станислав Васильев
Источник задачи: X командный Чемпионат Урала по спортивному программированию, 24-25 марта 2006 года