Король Байтазар считает, что Байтотия — земля, полная красивых достопримечательностей — должна привлечь множество туристов, которые должны потратить много денег, которые в конечном счете должны найти свой путь в королевскую казну. Но реальность далека от мечты. Поэтому король поручил своему советнику изучить этот вопрос. Советник выяснило, что иностранцы держаться подальше от Байтотии из-за ее плохой дорожной сети. В Байтотии \(n\) городов соединенных \(m\) двусторонними дорогами. Не гарантируется, что от каждого города можно добраться от любого другого города. Советник отметил, что нынешний дорожная сеть не позволяет делать длительные путешествия. А именно, где бы вы не начали поездку, невозможно посетить более 10 городов не прохождения через какой-то город два раза. Из-за ограниченных средств в казне, новые дороги построить нельзя. Вместо этого, Байтазар решил создать сеть туристическо-информационных пунктов (ТИП), которые будут рекламировать короткие путешествия. Для каждого города должен быть ТИП либо в нем, либо в одном из городов, непосредственно связанных с ним дорогой. Кроме того, известна стоимость строительства ТИПа в каждом из городов. Помогите королю найти самый дешевый спосою построить ТИПы, так, чтобы это условие удовлетворялось.