0    1    2    3    4      min1          min2
0    0    1   (2)   3    1      1                
1    1    0  (10)  (7)   1      1+1           10+7 
2   (2) (10)   0   15    3      2+3          10+15
3    3   (7)  15    0   (2)     2+3           7+15
4    1    1    3   (2)   0      1                
                             
shortest0-4:     length:21
0--2--1--3--4
  2 10  7  2   

lower_bound1: sum(min1)/2  =  14/2  =  7

lower_bound2: 19 = sum(min2)/2 - 15 + 1 + 1
   (excluding col 0 and 4 for double rows, striking the maximum)