{-# LANGUAGE BangPatterns #-}
import Control.Arrow
import Control.Monad.Fix
import Data.Foldable
import qualified Data.Vector as V
import qualified Data.Vector.Mutable as VMM
import qualified Data.Vector.Unboxed as VU
import qualified Data.Vector.Unboxed.Mutable as VM
import qualified Data.ByteString.Char8 as B
import Data.ByteString.Internal (accursedUnutterablePerformIO)
import qualified Data.Set as S
import System.IO.Unsafe
import Debug.Trace

uread :: VU.Unbox a => Int -> VM.IOVector a -> a
uread !i !v = accursedUnutterablePerformIO $ VM.unsafeRead v i

uwrite :: VU.Unbox a => Int -> a -> VM.IOVector a -> VM.IOVector a
uwrite !i !a !v = accursedUnutterablePerformIO $ VM.unsafeWrite v i a >> return v

umodify :: VU.Unbox a => Int -> (a -> a) -> VM.IOVector a -> VM.IOVector a
umodify !i !f !v = accursedUnutterablePerformIO $ VM.unsafeModify v f i >> return v

uthaw :: VU.Unbox a => VU.Vector a -> VM.IOVector a
uthaw !v = accursedUnutterablePerformIO $ VU.unsafeThaw v

ufreeze :: VU.Unbox a => VM.IOVector a -> VU.Vector a
ufreeze !v = accursedUnutterablePerformIO $ VU.unsafeFreeze v

dijkstra
  :: Int  -- ^ nodes
  -> V.Vector (VU.Vector (Int, Double))  -- ^ edges from i-th node: (end, cost)
  -> Int  -- ^ start node
  -> VU.Vector Double  -- ^ constructed graph
dijkstra !n !edges !s = ufreeze $ fst $ fix
  ( \f (costs, visited) -> case findMinView costs visited of
    (-1) -> (costs,visited)
    n ->
      let visited' = uwrite n True visited
          c = uread n costs
      in if c <= uread n costs
          then f $ flip (,) visited' $ VU.foldl'
            ( \cs (e,ec) ->
              let c' = c + ec in 
                if c' < uread e costs
                  then uwrite e c' cs
                  else cs
            )
            costs
            (edges V.! n)
          else f (costs, visited')
  )
  (costs0, visited0)
 where
  costs0 :: VM.IOVector Double
  costs0 = uwrite s 0 (uthaw $ VU.replicate n (2^60))

  visited0 :: VM.IOVector Bool
  visited0 = uthaw $ VU.replicate n False

  findMinView :: VM.IOVector Double -> VM.IOVector Bool -> Int
  findMinView !vec !visited = fst $ foldl' (\(j,acc) i -> let a = uread i vec; b = uread i visited in if not b && a < acc then (i,a) else (j,acc)) (-1,fromIntegral (maxBound :: Int)) [0..n-1]

solve :: Int -> Int -> Int -> Int -> Int -> VU.Vector (Int, Int, Int) -> Double
solve xs ys xt yt n !xyr = graph VU.! (n + 1)
 where
  big = fromIntegral (maxBound :: Int)

  dist2C :: (Int, Int, Int) -> (Int, Int, Int) -> Double
  dist2C (x1, y1, r1) (x2, y2, r2) =
    ( sqrt (fromIntegral $ (x1 - x2) ^ 2 + (y1 - y2) ^ 2)
      - fromIntegral (r1 + r2)
      )
      `max` 0

  toIndex (!i,!j)
    | i <= j = i * (n + 2) + j
    | otherwise = toIndex (j,i)

  distMemo = ufreeze $ foldl'
    ( \acc (i, j) ->
      let c1 = if i == n
            then (xs, ys, 0)
            else if i == n + 1 then (xt, yt, 0) else xyr VU.! i
          c2 = if j == n
            then (xs, ys, 0)
            else if j == n + 1 then (xt, yt, 0) else xyr VU.! j
      in  uwrite (toIndex (i, j)) (dist2C c1 c2) acc
    )
    (uthaw $ VU.replicate ((n + 2) * (n + 2)) big)
    [ (i, j) | i <- [0 .. n + 1], j <- [i+1 .. n + 1] ]
  edges = accursedUnutterablePerformIO $ V.generateM
    (n + 2)
    ( \e -> return $! VU.map (\i -> (i, distMemo VU.! toIndex (i, e)))
      $ VU.fromList [0 .. n + 1]
    )
  graph = dijkstra (n + 2) edges n

main = do
  let readInt = fmap (second B.tail) . B.readInt

  (xs, ys, xt, yt) <-
    (\vec -> (vec VU.! 0, vec VU.! 1, vec VU.! 2, vec VU.! 3))
    .   VU.unfoldrN 4 readInt
    <$> B.getLine
  n   <- (\vec -> (vec VU.! 0)) . VU.unfoldrN 1 readInt <$> B.getLine
  xyr <-
    VU.replicateM n
    $   (\vec -> (vec VU.! 0, vec VU.! 1, vec VU.! 2))
    .   VU.unfoldrN 3 readInt
    <$> B.getLine
  print $ solve xs ys xt yt n xyr


Measured memory_bytes: 25596