The coffee machine

[admin]

Jason, as the office manager of a big company, wants to improve the productivity of the employees by making sure they never run out of caffeine. So for that purpose he has decided to buy 2 coffee machines. Now he's wondering where to place them in order to minimize the distance of the employees to either machine. So he's looking for your help to solve the problem for him so that he can fully blame you if anything goes wrong and take the full credit if everything goes well.

Go to puzzle

[Francesco Laurita]

The sample input looks wrong to me:

8 12
confroom restroom 437
confroom hroffice 663
hroffice restroom 480
restroom printer 253
lobby hroffice 855
stairs printer 257
printer janitorial 951
restroom garage 956
garage janitorial 596
janitorial stairs 965
restroom confroom 715
janitorial lobby 732

If walk from confroom to restroom has a cost of 437,IMHO also the cost from restroom to confroom should be 437 since the path is the same.
Am I wrong?

[admin]

This has been answered here:
viewtopic.php?f=5&t=51

[Alexey Solodovnikov]

Just a small hint - a java solution gets better amount of the points than the same python solution (1600 vs 1422 points).