Maximize the Revenue

In a country there are $N$ cities numbered $1$ to $N$ and $M$ bidirectional roads connecting all these cities(i.e. There exists a path from every city to every other city). Unfortunately all the roads and tolls on these roads were damaged due to floods. Now the government has to reconstruct these roads so that people can travel from one city to another and they also need to set up toll gates to g