Придворный волшебник Ирдис попросил о помощи своего бывшего ученика полуэльфа Дезмонда, долгие годы прожившего в изгнании в землях людей. Дезмонд же, понимая, что в одиночку ему не справиться, отправился к своему другу, человеку-воину по имени Торвальд, с которым познакомился во время одного из военных походов.

Чтобы не тратить время на пешие прогулки, Дезмонд решил перемещаться по астральному плану, в котором есть n помещений. Между помещениями есть m астральных коридоров, по j-му из которых путник может мгновенно перемещаться между a_j-ым и b_j-ым помещениями. j-й коридор также характеризуется своей энергией возмущения c_j.

Дезмонд знает схему астральных коридоров и уже занумеровал астральные помещения так, что после входа в астрал он окажется в помещении номер 1, а чтобы попасть к Торвальду, нужно переместиться по плану в помещение номер n, а оттуда покинуть астрал.

Однако, между нами говоря, это всего лишь второй выход Дезмонда в астрал. В первый раз он выходил со своим наставником Ирдисом, и тот рассказывал ему о технике нахождения подходящего астрального уровня, о плотностях потоков магической энергии и всё такое, но Дезмонд тогда ничего не понял и запомнил из всей теории магических перемещений только основной вывод: перемещение по астральному плану не требует маны, но на выход из астрала расходуется количество маны, равное второй по величине энергии возмущения среди всех коридоров, которые вы проходили, будучи в астрале. Если же вы прошли в астрале меньше двух коридоров, то маны на выход из астрала не требуется.

Конечно же, Дезмонд хотел бы затратить как можно меньше маны на дорогу до Торвальда — силы ему ещё пригодятся, когда они вступят в борьбу с захватчиком Деймосом. Поэтому необходимо найти, сколько маны придётся израсходовать.