Задача M343

Условие

В некоторых государстве города сединины дорогами. Длина любои дороги меньше 500 км и из любого города в любои другой можно попасть, проехав по дорогам менее 500 км. Когда одну дорогу закрыли на ремонт, выяснили, что из любого города можно проехать в любои другой по оставшимся дорогам. Докажите, что это можно сделать, проехав не более 1500 км.

C. Л. Елисеев