The longest needle

We define a needle-like primitive triangle as follows:

It has 3 vertices on lattice points

It has no other lattice points inside or onside

Find such a triangle with the maximum possible perimeter in x² + y² = R² circle for R=123456789. Answer format: a²+b²+c² where a,b,c are the sides of the triangle Example: 136 if R=5 For instance for the triangle with vertices (-4,-2),(1,1),(4,3) [My timing: <40s]