Задача М459‍‍

В некоторой стране из каждого города в любой другой можно проехать, минуя остальные города. Известна стоимость каждого такого проезда. Составлены два маршрута поездки по городам страны. В каждый из этих маршрутов каждый город входит ровно по одному разу. При составлении первого маршрута руководствовались следующим принципом: начальный пункт маршрута выбирается произвольно, а на каждом следующем шаге среди городов, через которые маршрут ещё не проходил, выбирается тот, поездка в который из предыдущего города имеет наименьшую стоимость (если таких городов несколько, то выбирается любой из них); и так до тех пор, пока не будут пройдены все города. При составлении второго маршрута начальный город тоже выбирается произвольно, а на каждом следующем шаге среди городов, через которые маршрут ещё не проходил, выбирается тот, поездка в который из предыдущего города имеет наибольшую стоимость. Докажите, что общая стоимость проезда по первому маршруту не больше общей стоимости проезда по второму маршруту.