Low Cost Road Network

Low Cost Road Network

This task was proposed and prepared, text and code, by Clive Fraser aka CSFPython - thanks a lot!

The land of Erewhon is very mountainous and travel between villages is possible only by narrow mule paths. This means that trade between the villages is very difficult. The king decided to change that by linking the villages with simple roads that would allow the passage of a donkey pulling a cart. This would require the building of a number of bridges as well as preparing a solid bed for the road - so the project is really expensive!

To keep costs as low as possible the king's first idea was to link all of the villages by a single continuous road. He drew up specifications for the quality of the road and got his builders to estimate the cost. The cost was rather more than he had expected.

After some thought he decided that it was not necessary to have one continuous road. Any system of roads that made it possible to travel between any pair of villages would be acceptable. He also decided to invite all of the builders in the kingdom to submit costs for potential roads which would meet his specifications. The submitted cost could relate to a road link between any pair of villages in the kingdom.

The king was very pleased with the response to this invitation. He soon had a large list of costs for proposed roads. The problem now is to choose the set of roads which will cost the least. Please refer to the example below to fully understand what is required.

1. The first line has a single integer N which is the number of villages. The initially proposed continuous road would need N-1 sections to run through all of the villages.
2. The second line contains the initial N-1 costs for these road sections. For convenience we will number the villages from 0, 1, 2, ..., N-1. So the proposed cost of building a road between villages 0 and 1 is 33993 silver pieces; the cost for the road between villages 1 and 2 is 81906 silver pieces and so on. The total proposed cost is 260009 silver piesces.
3. The next line of data contains a single integer M. This is the number of additional road costings which the king has now collected. (Note that these do not include the costings already given)
4. Exactly M lines of data follow this. Each line contains three integers. The first two are the numbers of the villages to be linked and the third is the proposed cost.

You now need to consider all proposed roads (including the initial N-1 sections). Where several costings have been given for a road between the same pair of villages, only the cheapest (if any) is likely to be chosen.

You need to find the cheapest network which connects all of the villages and then work out how much cheaper this is than the cost of the original proposed road. It is this cost saving which is required for the answer.

Example

Using the example below the cheapest network contains the following roads, with costs in brackets:

0-1 (33993), 0-3 (51594), 2-3 (15767), 2-4 (32584), 4-6(34108) and 5-6 (32865)

These have a total cost of 200911, giving a cost saving of 59098 silver pieces.

Example input data:

7
33993 81906 15767 34018 61460 32865
20
2 6 44915
4 0 91710
0 3 51594
4 2 32584
6 4 34108
4 5 58757
2 1 69940
6 5 33320
6 4 37759
5 6 34478
0 6 75539
5 4 59941
4 0 92877
0 5 62171
0 6 68991
3 6 40877
0 5 59027
2 6 51077
3 6 40683
3 2 17229