In[1]:= AbsoluteTiming[
 f[{x_, y_, z_}] := (2 z > x + y) &&
   AllTrue[{x + y - z, z - y, x - z}, IntegerQ[Sqrt[#]] &];

 counter = 0;
 myList = {};
 For[a = 4, counter == 0, a++, aa = a^2;
  For[k = 1, a - 2 k > 0, k++, bb = (a - 2 k)^2;
   For[c = a - 2 k + 1, c < a, c++,
    If[f[{aa, bb, c^2}], AppendTo[myList, {aa, bb, c^2}];
     counter++]
    ]]];

 g[x_, y_, z_] := z + (x - y)/2;
 ans = Min[g @@@ myList]]

Out[1]= {312.89, 1006193}