№ 13767

В стране $n\gt 100$ городов и пока нет дорог. Правительство наугад определяет стоимость строительства дороги (с двусторонним движением) между каждыми двумя городами, используя по разу все суммы от 1 до $n(n-1)/2$ талеров (все варианты равновероятны). Мэр каждого города выбирает самую дешёвую из $n-1$ возможных дорог, идущих из этого города, и она строится (это может быть взаимным желанием мэров обоих соединяемых городов или только одного из двух).
После строительства этих дорог города оказываются разбиты на $M$ компонент связности (между городами одной компоненты связности можно добраться по построенным дорогам, возможно, с пересадками, а между городами разных компонент — нельзя). Найдите математическое ожидание случайной величины $M$.