Мадока не смогла выиграть олимпиаду Когнитивные технологии, поэтому попытается выиграть хотя бы своего лучшего друга. Они будут играть в следующую игру.

У Мадоки есть связный взвешенный неориентированный граф, состоящий из $$$n$$$ вершин, пронумерованных числами от $$$1$$$ до $$$n$$$. Она выбирает в нём подмножество из $$$n$$$ рёбер, таких, что подграф, образованный этими рёбрами и вершинами на их концах, является связным. Затем второй игрок выбирает из этого подмножества ребро, после удаления которого подграф останется связным, и удаляет его.

Счётом игры называется суммарный вес оставшихся $$$n - 1$$$ рёбер в этом подмножестве. Первый игрок (Мадока) хочет минимизировать счёт, тогда как второй игрок (лучший друг Мадоки) хочет его максимизировать.

Мадока хочет узнать счёт игры, при условии, что оба игрока играют оптимально. Помогите ей с этим.