Маша хочет открыть свою пекарню и печь пирожки в одном из n городов, пронумерованных от 1 до n. Также существует m двунаправленных дорог, каждая из которых соединяет некоторую пару городов. Чтобы печь пирожки, Маше нужно наладить регулярные поставки муки со склада. Всего существует k складов, расположенных в различных городах с номерами a₁, a₂, ..., a_k.

К сожалению, законы страны, в которой живет Маша, не позволяют открывать пекарню в любом из городов, где есть склад. Открыть ее можно только в одном из остальных n - k городах, при этом, само собой, за доставку муки нужно платить — за каждый километр пути от склада до пекарни Маша заплатит 1 рубль.

Формально, Маша заплатит x рублей, если она откроет пекарню в городе b (a_i ≠ b для любого 1 ≤ i ≤ k) и выберет склад в городе s (s = a_j для некоторого 1 ≤ j ≤ k), а между городами b и s существует путь по дорогам суммарной длины x (если путей несколько, Маша вправе выбирать, какой именно путь будет использован).

Маша — крайне бережливый и рациональный человек. Ее интересует тот город, при открытии пекарни в котором (и выборе одного из k складов и пути между городом с пекарней и городом со складом) платить за доставку ей придется меньше всего. Помогите Маше найти сумму, которую она заплатит в этом случае.