Snowplough Turns

Here I will post a series of (mostly) simple challenges to amuse you in the run-up to Christmas. I'll try to post one each weekday.
DDRM
Posts: 398
Joined: Mon 02 Apr 2018, 18:04

Snowplough Turns

Post by DDRM »

Santa’s toy factory site has been buried in snow! It is necessary to clear paths (blue lines, with numbers) between the different workshops (shown by letters), but it is hard work, and the elves are very busy, so they only want to clear the easiest route that will ensure all sites can be reached. The diagram below shows the effort involved for each path, but not all routes need to be cleared. What is the lowest number of elf-hours that will allow all sites to be reached from any other?

Hint: you are looking for a “minimum spanning tree”: there is a very “Prim” algorithm for this!
You do not have the required permissions to view the files attached to this post.