The Travelling PokeMan
PiHan is a die-hard Pokemon Go player.
In his town, there are 16 PokeStops, including his own house which is also one! Being the busy problem solver on Brilliant, he wants to route through them in the fastest possible way, and come back to his house. He does not want to pass through a PokeStop on his route more than once.
What is the minimum number of minutes he would be spending on this tour?
Here is the matrix of the number of minutes it takes to travel from a pokestop to another. The \(j\)th entry on the \(i\)th line is the distance in minutes from stop \(i\) to stop \(j\). PiHan's house is stop 1.