Explanation for Centroid:
Find a node such that the sum of distance from that node to every other node is minimised. Output the sum.

Eg. For sample input:

The node is 2 since shortest distance from 2 to 1 is 5, shortest distance from 2 to 3 is 5 and shortest distance from 2 to 4 is 6.

5+5+6 = 16, which is the minimum sum across all nodes.