Хань живет в общей квартире. Там живет \(n\) человек (включая Ханя), у каждого из которых есть собственный холодильник.
\(n\) холодильников защищены несколькими цепями. Каждая цепь соединяет два различных холодильника и защищена цифровым замком. Владелец холодильника знает коды доступа всех связанных с ним цепей. Холодильник может быть открыт только в том случае, если все цепи, подключенные к нему, разблокированы. Например, если холодильник вообще не имеет связанных с ним цепей, то его может открыть любой из \(n\) человек.
Например, на рисунке есть \(n=4\) людей и \(5\) цепей. Первый человек знает пароль для двух цепей: \(1-4\) и \(1-2\). \(1\)-й холодильник может открыть его владелец (\(1\)-й человек), а также \(2\)-й и \(4\)-й (работая сообща) могут его открыть. Цены этих холодильников равны \(a_1, a_2, \ldots, a_n\). Чтобы сделать цепь, соединяющую холодильники \(u\) и \(v\), вы должны заплатить \(a_u + a_v\) долларов. Обратите внимание, что владелец квартиры позволяет вам сделать несколько цепей, соединяющих одну и ту же пару холодильников.
Хозяин квартиры, в которой живет Хань, просит вас создать ровно \(m\) цепей, чтобы все холодильники были защищены. Холодильник является защищенным тогда и только тогда, когда из \(n\) людей, живущих в квартире, только владелец холодильника может открыть его (то есть больше никто, действуя самостоятельно, не сможет его открыть). Другими словами, \(i\)-й холодильник не защищен, если существует человек \(j\) (\(i \ne j\)) такой, что \(j\) в одиночку сможет открыть \(i\)-й холодильник.
Например, на рисунке все холодильники защищены. С другой стороны, если есть \(n=2\) холодильника и только одна цепь (которая их соединяет), то оба холодильника не являются защищенными (оба холодильника могут быть открыты не только его владельцем, но и другим человеком).
Конечно, владелец хочет минимизировать общую стоимость всех цепей. Определите, существует ли какой-либо способ сделать ровно \(m\) цепей, и, если да, выведите любое решение, которое минимизирует суммарную стоимость.