{-# 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 = accursedUnutterablePerformIO . VU.unsafeThaw

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

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 $ snd $ fix
  ( \f (nodes, costs) -> case S.minView nodes of
    Nothing              -> (S.empty, costs)
    Just ((c, n), nodes) -> if c <= uread n costs
      then
        let es = edges V.! n
        in  f $ VU.foldl'
              ( \(!ns, !cs) (!e, !ec) ->
                let c' = c + ec
                in  c' `seq` if c' < uread e costs
                      then
                        let a = S.insert (c', e) ns
                            b = uwrite e c' cs
                        in  a `seq` b `seq` (a, b)
                      else (ns, cs)
              )
              (nodes, costs)
              es
      else f (nodes, costs)
  )
  (nodes0, costs0)
 where
  costs0 :: VM.IOVector Double
  costs0 = uwrite s 0 (uthaw $ VU.replicate n $ fromIntegral (maxBound :: Int))

  nodes0 :: S.Set (Double, Int)
  nodes0 = S.singleton (0, s)

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 * (n + 2) + j

  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 <- [0 .. n + 1], i /= j ]
  edges = V.force $ V.generate
    (n + 2)
    ( \e -> 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: 104444