Первое решение. Уберём все экспресслы, а затем начнём запускать их обратно по одному в порядке возрастания цены (т. е. первым запустим самый дешёвый, вторым — самый дешёвый из остальных, и т. д.). В каждый момент в каждом городе будем писать максимальное количество экспрессов, на которых можно последовательно проехать, начав из этого города, так, чтобы цены проезда монотонно убывали.
В начальный момент все числа в городах равны нулю. Пусть в некоторый момент мы вводим экспресс, соединяющий города $A$ и $B$, в которых до этого были написаны числа $a$ и $b$ соответственно. После введения нового экспресса в $A$ будет число, не меньше $b + 1$ (ибо теперь из $A$ можно проехать новым экспрессом в $B$, а затем по маршруту длины $b$, начинавшемуся из $B$). Аналогично, в $B$ будет написано число, не меньшее $a + 1$. Поэтому сумма чисел в $A$ и $B$ увеличится хотя бы на $2$, а числа в остальных городах не уменьшатся. Значит, и сумма всех чисел в городах увеличится хотя бы на $2$.

Таким образом, когда все $n(n-1)/2$ экспрессов будут введены, сумма чисел в городах станет не меньше, чем $2 \cdot n(n-1)/2 = n(n-1)$. Значит, хотя бы в одном городе будет число, не меньшее $n-1$. Это и означает наличие требуемого маршрута из этого города.

Второе решение. Разделим каждый экспресс, курсирующий между $A$ и $B$, на два — идущий из $A$ в $B$, и идущий из $B$ в $A$. Получились $n(n-1)$ полуэкспрессов. Мы построим $n$ выделенных маршрутов (по одному, начинающемуся в каждом городе) так, чтобы цена поездки на каждом монотонно убывала, и каждый полуэкспресс содержался бы хотя бы в одном выделенном маршруте. Тогда один из выделенных маршрутов будет содержать не менее $n-1$ полуэкспресса, что и требовалось.

Выделенный маршрут, начинающийся в городе $A$, выглядит так. Пусть $A_0 = A$. Рассмотрим все полуэкспрессы $A_0X$, выходящие из $A_0$, и выберем из них полуэкспресс $A_0A_1$ максимальной цены $a_1$. Затем рассмотрим все полуэкспрессы $A_1Y$, выходящие из $A_1$, цена которых меньше $a_1$; если такие есть, выберем из них полуэкспресс $A_1A_2$ максимальной цены $a_2$, и т.д. Маршрут заканчивается полуэкспрессом $A_{k-1}A_k$, если из $A_k$ не выходит полуэкспрессов с ценой, меньшей $a_k$.

Осталось показать, что каждый полуэкспресс $BC$ попадёт хотя бы в один из выделенных маршрутов. Положим $B_1 = B$, $B_0 = C$, и пусть $b_1$ — цена $BC$. Рассмотрим все полуэкспрессы $XB_1$, ведущие в $B_1$, с ценой, большей $b_1$. Если такие есть, то выберем из них полуэкспресс $B_2B_1$ наименьшей цены $b_2$. Далее рассмотрим все полуэкспрессы $YB_2$, ведущие в $B_2$, с ценой, большей $b_2$. Выберем из них полуэкспресс $B_3B_2$ наименьшей цены $b_3$, и т.д. Этот процесс выбора закончится, когда при некотором $k$ полуэкспресс $B_kB_{k-1}$ — это полуэкспресс максимальной цены, выходящий из $B_k$. Тогда, согласно нашему построению, выделенный маршрут, выходящий из $B_k$, последовательно пройдёт через $B_{k-1}, \dots, B_1, B_0$, то есть будет содержать экспресс $BC$, что и требовалось.