La compañía de aviación de Ryan ofrece sus servicios en $N$ ciudades importantes del mundo. Se enorgullece sobremanera de la calidad de sus ofertas y de sus precios tan bajos.
Actualmente ofrece $N-1$ vuelos de forma tal que se puede viajar entre todo par de ciudades tomando varios de ellos. El próximo plan de la compañía es crear un vuelo directo entre todo par de ciudades que no tengan uno hasta el momento. Uno de los objetivos es mantener los precios bajos y por tanto se quiere que la suma de los precios de todos los vuelos sea mínima, aunque en ningún caso el precio de un vuelo ya existente se modificará. Una restricción importante, que piensa cumplir la empresa, para evitar que los precios bajen demasiado, es escoger estos de forma tal que todo subconjunto de $N - 1$ vuelos, donde al menos uno de ellos es nuevo y que permita viajar entre cualquier par de ciudades ha de tener una suma de precios mayor que la suma de los precios de los vuelos actuales.