The country of Truckski is located in a rugged, mountainous region, and the geological condition has engendered a wide range of issues. The challenging terrain separates the different states in the country, resulting in an extremely inconvenient inter-state commute and more crucially a lack of central governmental control. Adding on top of that is a rampant crime rate that increases annually, and this severely disrupts the everyday lives of innocent citizens. A recent protest finally shed light on the situation, as the newly elected president has announced an ambitious project to resolve these issues. Her plan consists of two major components. The first is the construction of high-speed railways between the states to facilitate better connections and unity across the country. Since the states are mostly running independently from each other, to construct a railway between states (u) and (v), the government has to pay a fee of (a_u + a_v) dollars, with (a_u) dollars given to state (u) and (a_v) dollars given to state (v). The railway operates bidirectionally, meaning that once it is built, people from state (u) can now travel to state (v) and vice versa. A railway can be built between almost any pair of states, except for (m) particular pairs for which the terrain dividing them is so treacherous that the construction of a direct railroad between the two states becomes impossible. The second component of the project is to build a centralized prison that manages all criminals across the country. Given the large number of estimated prisoners, the president decided to pick one of the states to build the central prison and sever the connection from the state to the rest of the country. Given the above, the president would like to search for the minimum cost plan to construct railroads between the states so that: the state with the central prison should not have any railway connecting it to any other states, and all the oth