1000 городов Тридевятого царства соединены авиаперелётами, причём между любыми двумя городами есть рейс. Также для любых двух городов A и B на любом пути из A в B, проходящем через другие города, найдётся перелёт, который по протяжённости будет равен или короче перелёта из A в B. Какое наибольшее количество перелётов могут иметь попарно различную протяжённость?