AtCoder Regular Contest 064 - Cosmic Rays

On the xy-plane, Snuke is going to travel from the point (x_s, y_s) to the point (x_t, y_t).
He can move in arbitrary directions with speed 1.
Here, we will consider him as a point without size.
There are N circular barriers deployed on the plane.
The center and the radius of the i-th barrier are (x_i, y_i) and r_i, respectively.
The barriers may overlap or contain each other.
A point on the plane is exposed to cosmic rays if the point is not within any of the barriers.
Snuke wants to avoid exposure to cosmic rays as much as possible during the travel.
Find the minimum possible duration of time he is exposed to cosmic rays during the travel.

-----Constraints-----
 - All input values are integers.
 - -10^9 ≤ x_s, y_s, x_t, y_t ≤ 10^9
 - (x_s, y_s) ≠ (x_t, y_t)
 - 1≤N≤1,000
 - -10^9 ≤ x_i, y_i ≤ 10^9
 - 1 ≤ r_i ≤ 10^9

-----Input-----
The input is given from Standard Input in the following format:
x_s y_s x_t y_t
N
x_1 y_1 r_1
x_2 y_2 r_2
:
x_N y_N r_N

-----Output-----
Print the minimum possible duration of time Snuke is exposed to cosmic rays during the travel.
The output is considered correct if the absolute or relative error is at most 10^{-9}.

-----Sample Input-----
-2 -2 2 2
1
0 0 1

-----Sample Output-----
3.6568542495

An optimal route is as follows:

Source: atcoder | Difficulty: HARD


Solutions:
import sys
input = sys.stdin.readline
(sx, sy, tx, ty) = list(map(int, input().split()))
n = int(input())
p = [(sx, sy, 0)]
for _ in range(n):
	(x, y, r) = list(map(int, input().split()))
	p.append((x, y, r))
p.append((tx, ty, 0))
n += 2
edge = [[] for _ in range(n)]
for i in range(n - 1):
	for j in range(i + 1, n):
		(sx, sy, sr) = p[i]
		(tx, ty, tr) = p[j]
		t = (abs(sx - tx) ** 2 + abs(sy - ty) ** 2) ** 0.5
		c = max(0, t - (sr + tr))
		edge[i].append((j, c))
		edge[j].append((i, c))
from heapq import heappop, heappush
inf = 10 ** 20
ans = [inf] * n
ans[0] = 0
root = [-1] * n
h = [(0, 0)]
while h:
	(c, v) = heappop(h)
	if ans[v] < c:
		continue
	for (u, t) in edge[v]:
		if c + t < ans[u]:
			ans[u] = c + t
			root[u] = v
			heappush(h, (c + t, u))
print(ans[n - 1])


import heapq
INFTY = 10 ** 10

def f(x, y):
	return ((x[0] - y[0]) ** 2 + (x[1] - y[1]) ** 2) ** 0.5
(xs, ys, xt, yt) = map(int, input().split())
N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]
A.insert(0, [xs, ys, 0])
A.append([xt, yt, 0])
dist = [INFTY for _ in range(N + 2)]
hist = [0 for _ in range(N + 2)]
heap = [(0, 0)]
dist[0] = 0
hist[0] = 1
while heap:
	(d, x) = heapq.heappop(heap)
	if dist[x] < d:
		continue
	hist[x] = 1
	for i in range(N + 2):
		if hist[i] == 0:
			if dist[i] > d + max(f(A[x][:2], A[i][:2]) - (A[x][2] + A[i][2]), 0):
				dist[i] = d + max(f(A[x][:2], A[i][:2]) - (A[x][2] + A[i][2]), 0)
				heapq.heappush(heap, (dist[i], i))
print(dist[N + 1])


def getN():
	return int(input())

def getNM():
	return map(int, input().split())

def getList():
	return list(map(int, input().split()))

def getArray(intn):
	return [int(input()) for i in range(intn)]

def input():
	return sys.stdin.readline().rstrip()

def rand_N(ran1, ran2):
	return random.randint(ran1, ran2)

def rand_List(ran1, ran2, rantime):
	return [random.randint(ran1, ran2) for i in range(rantime)]

def rand_ints_nodup(ran1, ran2, rantime):
	ns = []
	while len(ns) < rantime:
		n = random.randint(ran1, ran2)
		if not n in ns:
			ns.append(n)
	return sorted(ns)

def rand_query(ran1, ran2, rantime):
	r_query = []
	while len(r_query) < rantime:
		n_q = rand_ints_nodup(ran1, ran2, 2)
		if not n_q in r_query:
			r_query.append(n_q)
	return sorted(r_query)
from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
from heapq import heapify, heappop, heappush
from math import sqrt
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right
import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7
(x1, y1, x2, y2) = getNM()
place = [(x1, y1, 0)]
N = getN()
for i in range(N):
	(x, y, r) = getNM()
	place.append((x, y, r))
place.append((x2, y2, 0))
N += 2

def calc(x1, y1, x2, y2):
	return ((x1 - x2) ** 2 + (y1 - y2) ** 2) ** 0.5

def dijkstra(n, start):
	dist = [float('inf')] * n
	pos = [(0, start)]
	heapify(pos)
	dist[start] = 0
	while len(pos):
		(cost, u) = heappop(pos)
		if dist[u] < cost:
			continue
		for i in range(N):
			if i == u:
				continue
			dis = calc(place[u][0], place[u][1], place[i][0], place[i][1])
			opt = max(dis - place[u][2] - place[i][2], 0)
			if dist[u] + opt < dist[i]:
				dist[i] = dist[u] + opt
				heappush(pos, (dist[u] + opt, i))
	return dist
print(dijkstra(N, 0)[-1])


def dijkstra(s):
	d = [float('inf')] * n
	used = [False] * n
	d[s] = 0
	while True:
		v = -1
		for i in range(n):
			if not used[i] and v == -1:
				v = i
			elif not used[i] and d[i] < d[v]:
				v = i
		if v == -1:
			break
		used[v] = True
		for j in range(n):
			d[j] = min(d[j], d[v] + cost[v][j])
	return d
(sx, sy, gx, gy) = map(int, input().split())
n = int(input())
edge = [[sx, sy, 0]]
for i in range(n):
	(x, y, r) = map(int, input().split())
	edge.append([x, y, r])
edge.append([gx, gy, 0])
cost = [[0] * (n + 2) for _ in range(n + 2)]
for (j, k) in enumerate(edge):
	for (l, m) in enumerate(edge):
		if j == l:
			continue
		else:
			cost[j][l] = max(((k[0] - m[0]) ** 2 + (k[1] - m[1]) ** 2) ** 0.5 - k[2] - m[2], 0)
n += 2
res = dijkstra(0)
print(res[-1])


import sys
import time
input = sys.stdin.buffer.readline

def getN():
	return int(input())

def getNM():
	return map(int, input().split())

def getlist():
	return list(map(int, input().split()))
import math
import heapq
import bisect
from collections import defaultdict, Counter, deque
MOD = 10 ** 9 + 7
INF = 10 ** 21

def dijkstra(graph, start, n):
	h = []
	heapq.heappush(h, (0, start))
	costs = [INF for _ in range(n)]
	while h:
		(cost, cur) = heapq.heappop(h)
		if costs[cur] != INF:
			continue
		costs[cur] = cost
		for edge in graph[cur]:
			(ecost, tgt) = edge
			if costs[tgt] == INF:
				heapq.heappush(h, (cost + ecost, tgt))
	return costs

def dist(x1, y1, x2, y2):
	return math.sqrt(abs(x1 - x2) ** 2 + abs(y1 - y2) ** 2)

def main():
	(xs, ys, xe, ye) = getlist()
	N = getN()
	graph = [[] for i in range(N + 3)]
	circles = []
	circles.append([xs, ys, 0])
	circles.append([xe, ye, 0])
	for i in range(N):
		circles.append(getlist())
	for i in range(N + 1):
		for j in range(i + 1, N + 2):
			(x1, y1, r1) = circles[i]
			(x2, y2, r2) = circles[j]
			ray = max(dist(x1, y1, x2, y2) - r1 - r2, 0)
			graph[i].append((ray, j))
			graph[j].append((ray, i))
	print(dijkstra(graph, 0, N + 2)[1])
main()


(sx, sy, tx, ty) = map(int, input().split())
n = int(input())
l = [list(map(int, input().split())) for i in range(n)]
l.append([sx, sy, 0])
l.append([tx, ty, 0])

def dijkstra(s, n, cost):
	d = [float('inf')] * n
	used = [False] * n
	d[s] = 0
	while True:
		v = -1
		for i in range(n):
			if not used[i] and v == -1:
				v = i
			elif not used[i] and d[i] < d[v]:
				v = i
		if v == -1:
			break
		used[v] = True
		for j in range(n):
			d[j] = min(d[j], d[v] + cost[v][j])
	return d
cost = [[float('inf') for i in range(n + 2)] for i in range(n + 2)]
for i in range(n + 2):
	for j in range(n + 2):
		cost[i][j] = max(((l[i][0] - l[j][0]) ** 2 + (l[i][1] - l[j][1]) ** 2) ** 0.5 - l[i][2] - l[j][2], 0)
		cost[j][i] = max(((l[i][0] - l[j][0]) ** 2 + (l[i][1] - l[j][1]) ** 2) ** 0.5 - l[i][2] - l[j][2], 0)
print(dijkstra(n, n + 2, cost)[n + 1])


import heapq

def dijkstra(s, path):
	inf = float('inf')
	n = len(path)
	d = [inf for i in range(n)]
	d[s] = 0
	q = [(0, s)]
	heapq.heapify(q)
	while q:
		(c, p) = heapq.heappop(q)
		if d[p] < c:
			continue
		for (cost, to) in path[p]:
			if d[to] > d[p] + cost:
				d[to] = d[p] + cost
				heapq.heappush(q, (d[to], to))
	return d
(xs, ys, xt, yt) = map(int, input().split())
n = int(input())
barrier = [list(map(int, input().split())) for i in range(n)]
barrier = [[xs, ys, 0]] + barrier + [[xt, yt, 0]]
n += 2
path = [[] for i in range(n)]
for i in range(n):
	for j in range(i + 1, n):
		length = max(((barrier[i][0] - barrier[j][0]) ** 2 + (barrier[i][1] - barrier[j][1]) ** 2) ** 0.5 - barrier[i][2] - barrier[j][2], 0)
		path[i].append([length, j])
		path[j].append([length, i])
d = dijkstra(0, path)
print(d[-1])


import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10 ** 9))
write = lambda x: sys.stdout.write(x + '\n')
(xs, ys, xt, yt) = list(map(int, input().split()))
n = int(input())
xyr = [None] * (n + 2)
for i in range(n):
	xyr[i] = tuple(map(int, input().split()))
from itertools import product
data = []
rs = []
cs = []
s = n
t = n + 1
xyr[s] = (xs, ys, 0)
xyr[t] = (xt, yt, 0)
for (i, j) in product(range(n + 2), range(n + 2)):
	if i < j:
		d = max(0, ((xyr[i][0] - xyr[j][0]) ** 2 + (xyr[i][1] - xyr[j][1]) ** 2) ** 0.5 - (xyr[i][2] + xyr[j][2]))
		data.append(d)
		rs.append(i)
		cs.append(j)
import scipy.sparse
m = scipy.sparse.csr_matrix((data, (rs, cs)), shape=(n + 2, n + 2))
ans = scipy.sparse.csgraph.dijkstra(m, indices=t, directed=False)
print(ans[s])


import sys

def solve(x_s: int, y_s: int, x_t: int, y_t: int, N: int, x: 'List[int]', y: 'List[int]', r: 'List[int]'):
	import numpy as np
	from scipy.sparse import csr_matrix, coo_matrix
	from scipy.sparse.csgraph import dijkstra
	x.extend([x_s, x_t])
	y.extend([y_s, y_t])
	r.extend([0, 0])
	p = np.column_stack((x, y))
	diff = np.expand_dims(p, axis=1) - np.expand_dims(p, axis=0)
	dist = np.sqrt(np.sum(diff ** 2, axis=-1))
	mat = ((dist - r).T - r).clip(min=1e-20)
	return '{:.10f}'.format(dijkstra(csr_matrix(mat), indices=N)[N + 1])

def main():

	def iterate_tokens():
		for line in sys.stdin:
			for word in line.split():
				yield word
	tokens = iterate_tokens()
	x_s = int(next(tokens))
	y_s = int(next(tokens))
	x_t = int(next(tokens))
	y_t = int(next(tokens))
	N = int(next(tokens))
	x = [int()] * N
	y = [int()] * N
	r = [int()] * N
	for i in range(N):
		x[i] = int(next(tokens))
		y[i] = int(next(tokens))
		r[i] = int(next(tokens))
	print(solve(x_s, y_s, x_t, y_t, N, x, y, r))

def test():
	import doctest
	doctest.testmod()

def __starting_point():
	main()
__starting_point()


from collections import *
from itertools import *
from bisect import *
from heapq import *
import copy
idle = 10 ** 13
(xs, ys, xt, yt) = map(int, input().split())
N = int(input())
XYR = [list(map(int, input().split())) for i in range(N)]
XYR.append([xt, yt, 0])
XYR.append([xs, ys, 0])
kyori = [[0 for i in range(len(XYR))] for n in range(len(XYR))]
for i in range(len(XYR)):
	for m in range(i, len(XYR)):
		if i == m:
			t = 0
		else:
			(x1, y1, r1) = XYR[i]
			(x2, y2, r2) = XYR[m]
			t = max(((x2 - x1) ** 2 + (y2 - y1) ** 2) ** 0.5 - r1 - r2, 0)
		kyori[i][m] = t
		kyori[m][i] = t
stack = sorted(kyori[-1])
heapify(stack)
Pdic = {}
dic = {}
kyoriset = set()
for i in range(len(XYR)):
	a = kyori[-1][i]
	Pdic.update({i: a})
	if not a in kyoriset:
		kyoriset.add(a)
		dic.update({a: [i]})
	else:
		dic[a].append(i)
visited = set([len(XYR) - 1])
while stack:
	m = heappop(stack)
	a = dic[m].pop()
	if a == len(XYR) - 2:
		print(m)
		exit()
	if not a in visited:
		visited.add(a)
		for i in range(len(XYR)):
			nm = kyori[a][i] + m
			if Pdic[i] > nm:
				Pdic[i] = nm
				heappush(stack, nm)
				if not nm in kyoriset:
					kyoriset.add(nm)
					dic.update({nm: [i]})
				else:
					dic[nm].append(i)


class Dijkstra:

	class Edge:

		def __init__(self, _to, _cost):
			self.to = _to
			self.cost = _cost

	def __init__(self, V):
		self.G = [[] for i in range(V)]
		self._E = 0
		self._V = V

	@property
	def E(self):
		return self._E

	@property
	def V(self):
		return self._V

	def add(self, _from, _to, _cost):
		self.G[_from].append(self.Edge(_to, _cost))
		self._E += 1

	def shortest_path(self, s):
		import heapq
		que = []
		d = [10 ** 15] * self.V
		d[s] = 0
		heapq.heappush(que, (0, s))
		while len(que) != 0:
			(cost, v) = heapq.heappop(que)
			if d[v] < cost:
				continue
			for i in range(len(self.G[v])):
				e = self.G[v][i]
				if d[e.to] > d[v] + e.cost:
					d[e.to] = d[v] + e.cost
					heapq.heappush(que, (d[e.to], e.to))
		return d
from math import sqrt
(xs, ys, xt, yt) = map(int, input().split())
N = int(input())
pro = Dijkstra(N + 2)
node = [(xs, ys, 0), (xt, yt, 0)]
for i in range(0, N):
	(x, y, r) = map(int, input().split())
	node.append((x, y, r))
for i in range(0, N + 2):
	for j in range(0, N + 2):
		(x1, y1, r1) = node[i]
		(x2, y2, r2) = node[j]
		cost = max(0, sqrt((x1 - x2) ** 2 + (y1 - y2) ** 2) - r1 - r2)
		pro.add(i, j, cost)
ans = pro.shortest_path(0)
print(ans[1])


(xs, ys, xt, yt) = map(int, input().split())
n = int(input())
c = [(xs, ys, 0), (xt, yt, 0)]
for i in range(n):
	(x, y, r) = map(int, input().split())
	c.append((x, y, r))

def circle_circle(ax, ay, ar, bx, by, br):
	d = ((ax - bx) ** 2 + (ay - by) ** 2) ** 0.5
	return max(0, d - (ar + br))

def dijkstra(V, edges, root):
	import heapq
	visited = [False] * V
	nodes = [[] for i in range(V)]
	cost = [[] for i in range(V)]
	for e in edges:
		(s, t, d) = e
		nodes[s].append(t)
		cost[s].append(d)
	dist = [float('inf')] * V
	dist[root] = 0
	h = [(0, root)]
	while h:
		(c, v) = heapq.heappop(h)
		if visited[v]:
			continue
		visited[v] = True
		for i in range(n + 1):
			t = nodes[v][i]
			nc = c + cost[v][i]
			if dist[t] > nc:
				dist[t] = nc
				heapq.heappush(h, (nc, t))
	return dist
edges = []
for i in range(n + 1):
	for j in range(i + 1, n + 2):
		d = circle_circle(c[i][0], c[i][1], c[i][2], c[j][0], c[j][1], c[j][2])
		edges.append((i, j, d))
		edges.append((j, i, d))
dij = dijkstra(n + 2, edges, 0)
print(dij[1])


import sys
input = sys.stdin.readline

def dijkstra(s, n, Cost):
	D = [float('inf')] * n
	Visited = [False] * n
	D[s] = 0
	while True:
		v = -1
		for i in range(n):
			if not Visited[i] and v == -1:
				v = i
			elif not Visited[i] and D[i] < D[v]:
				v = i
		if v == -1:
			break
		Visited[v] = True
		for j in range(n):
			D[j] = min(D[j], D[v] + Cost[v][j])
	return D

def dist(V1, V2):
	return max(0, ((V2[0] - V1[0]) ** 2 + (V2[1] - V1[1]) ** 2) ** 0.5 - (V1[2] + V2[2]))
(sx, sy, gx, gy) = map(int, input().split())
n = int(input())
V = [(sx, sy, 0)] + [tuple(map(int, input().split())) for _ in range(n)] + [(gx, gy, 0)]
Cost = [[float('inf')] * (n + 2) for _ in range(n + 2)]
for i in range(n + 1):
	for j in range(i, n + 2):
		d = dist(V[i], V[j])
		Cost[i][j] = d
		Cost[j][i] = d
print(dijkstra(0, n + 2, Cost)[-1])


from heapq import heappop, heappush
from math import sqrt
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
INF = 10 ** 15

def dijkstra(E, s, g):
	d = [INF] * len(E)
	d[0] = 0
	queue = []
	heappush(queue, (0, s))
	while queue:
		(dist_v, v) = heappop(queue)
		if dist_v > d[v]:
			continue
		for (e, w) in E[v]:
			tmp = d[v] + w
			if tmp < d[e]:
				d[e] = tmp
				heappush(queue, (tmp, e))
	return d[g]

def main():
	(x_s, y_s, x_t, y_t) = list(map(int, readline().split()))
	(N, *xyr) = list(map(int, read().split()))
	XYR = []
	XYR.append((x_s, y_s, 0))
	XYR.append((x_t, y_t, 0))
	for (x, y, r) in zip(*[iter(xyr)] * 3):
		XYR.append((x, y, r))
	E = [[] for _ in range(N + 2)]
	for i in range(N + 1):
		(x_i, y_i, r_i) = XYR[i]
		for j in range(i + 1, N + 2):
			(x_j, y_j, r_j) = XYR[j]
			d = sqrt((x_i - x_j) ** 2 + (y_i - y_j) ** 2)
			d -= r_i + r_j
			d = max(0, d)
			E[i].append((j, d))
			E[j].append((i, d))
	ans = dijkstra(E, 0, 1)
	print(ans)

def __starting_point():
	main()
__starting_point()


from scipy.sparse.csgraph import csgraph_from_dense, dijkstra
(xs, ys, xt, yt) = map(int, input().split())
N = int(input())
xyr = [tuple(map(int, input().split())) for _ in range(N)]
xyr.append((xs, ys, 0))
xyr.append((xt, yt, 0))
b = [[-1] * (N + 2) for _ in range(N + 2)]
for i in range(N + 2):
	(x1, y1, r1) = xyr[i]
	for j in range(i + 1, N + 2):
		(x2, y2, r2) = xyr[j]
		r = max(0, ((x1 - x2) ** 2 + (y1 - y2) ** 2) ** 0.5 - (r1 + r2))
		b[i][j] = r
		b[j][i] = r
Graph = csgraph_from_dense(b, null_value=-1)
start = N
end = N + 1
print(dijkstra(Graph, indices=start)[end])


def main():
	from math import hypot
	import sys
	input = sys.stdin.readline
	inf = 1 << 60
	(xs, ys, xt, yt) = list(map(int, input().split()))
	N = int(input())

	def dist(p1, p2):
		d = hypot(p1[0] - p2[0], p1[1] - p2[1])
		return max(0, d - (p1[2] + p2[2]))
	ps = [(xs, ys, 0)]
	ps += (tuple(map(int, input().split())) for _ in range(N))
	ps += [(xt, yt, 0)]
	adj = [[inf] * (N + 2) for _ in range(N + 2)]
	for (i, p1) in enumerate(ps):
		for (j, p2) in enumerate(ps):
			if i <= j:
				break
			adj[i][j] = adj[j][i] = dist(p1, p2)

	def dijkstra(s):
		dist = [inf] * (N + 2)
		dist[s] = 0
		det = [0] * (N + 2)
		(c, v) = (0, s)
		det[s] = 1
		while True:
			for (u, dc) in enumerate(adj[v]):
				nc = c + dc
				if dist[u] <= nc:
					continue
				dist[u] = nc
			(c, v) = (-1, -1)
			for (u, d) in enumerate(dist):
				if det[u]:
					continue
				if ~v and c <= d:
					continue
				(c, v) = (d, u)
			if not ~v:
				break
			det[v] = 1
		return dist
	print(dijkstra(s=0)[N + 1])

def __starting_point():
	main()
__starting_point()


from heapq import heapify, heappop, heappush
(xs, ys, xt, yt) = map(int, input().split())
INF = float('inf')
N = int(input())
Z = []
for i in range(N):
	(x, y, r) = map(int, input().split())
	Z.append((x, y, r, i))
G = [[] for _ in range(N + 2)]
for i in range(N):
	dis = ((Z[i][0] - xs) ** 2 + (Z[i][1] - ys) ** 2) ** 0.5
	dis -= Z[i][2]
	dis = max(0, dis)
	G[0].append((dis, i + 1))
dis = ((xt - xs) ** 2 + (yt - ys) ** 2) ** 0.5
G[0].append((dis, N + 1))
for i in range(N):
	for j in range(N):
		if i == j:
			continue
		dis = ((Z[i][0] - Z[j][0]) ** 2 + (Z[i][1] - Z[j][1]) ** 2) ** 0.5
		dis -= Z[i][2] + Z[j][2]
		dis = max(0, dis)
		G[i + 1].append((dis, j + 1))
	dis = ((Z[i][0] - xt) ** 2 + (Z[i][1] - yt) ** 2) ** 0.5
	dis -= Z[i][2]
	dis = max(0, dis)
	G[i + 1].append((dis, N + 1))

def dijkstra_heap2(s, G):
	V = len(G)
	d = [INF for _ in range(V)]
	d[s] = 0
	PQ = []
	heappush(PQ, (0, s))
	while PQ:
		(c, v) = heappop(PQ)
		if d[v] < c:
			continue
		d[v] = c
		for (cost, u) in G[v]:
			if d[u] <= cost + d[v]:
				continue
			d[u] = cost + d[v]
			heappush(PQ, (d[u], u))
	return d
ret = dijkstra_heap2(0, G)
ans = ret[N + 1]
print(ans)


(XS, YS, XT, YT) = map(int, input().split())
N = int(input())
V = [[XS, YS, 0], [XT, YT, 0]]
for i in range(N):
	V.append(list(map(int, input().split())))
INF = 10 ** 12
G = [[INF] * len(V) for i in range(len(V))]

def d(a, b):
	return ((a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2) ** 0.5
for i in range(len(V)):
	G[i][i] = 0
	for j in range(len(V)):
		G[i][j] = max(0, d(V[i][:2], V[j][:2]) - V[i][2] - V[j][2])
D = [0] * len(V)
U = [0] * len(V)

def ijk(s):
	nonlocal D, U, G, V, INF
	for i in range(len(V)):
		D[i] = INF
		U[i] = False
	D[s] = 0
	v = 0
	while True:
		v = -1
		for i in range(len(V)):
			if not U[i] and (v == -1 or D[i] < D[v]):
				v = i
		if v == -1:
			break
		U[v] = True
		for i in range(len(V)):
			D[i] = min(D[i], D[v] + G[v][i])
ijk(0)
print(D[1])


import sys
from heapq import heapify, heappop, heappush
sr = lambda : sys.stdin.readline().rstrip()
ir = lambda : int(sr())
lr = lambda : list(map(int, sr().split()))
(sx, sy, gx, gy) = lr()
N = ir()
XYR = [[sx, sy, 0]] + [lr() for _ in range(N)] + [[gx, gy, 0]]
graph = [[] for _ in range(N + 2)]
for i in range(N + 2):
	for j in range(i + 1, N + 2):
		sp = XYR[i]
		ep = XYR[j]
		length = max(0, ((sp[0] - ep[0]) ** 2 + (sp[1] - ep[1]) ** 2) ** 0.5 - sp[2] - ep[2])
		graph[i].append((j, length))
		graph[j].append((i, length))

def dijkstra(start):
	INF = 10 ** 15
	dist = [INF] * (N + 2)
	dist[start] = 0
	que = [(0, start)]
	while que:
		(d, prev) = heappop(que)
		if dist[prev] < d:
			continue
		for (next, l) in graph[prev]:
			d1 = d + l
			if dist[next] > d1:
				dist[next] = d1
				heappush(que, (d1, next))
	return dist
dist = dijkstra(0)
answer = dist[N + 1]
print(answer)


def main():
	import sys
	input = sys.stdin.readline
	INF = 10 ** 10
	from math import sqrt
	(xs, ys, xg, yg) = map(int, input().split())
	N = int(input())
	XYR = [tuple(map(int, input().split())) for _ in range(N)]
	G = [[] for _ in range(N + 2)]

	def diff1(i, j):
		tmp = (XYR[i][0] - XYR[j][0]) ** 2 + (XYR[i][1] - XYR[j][1]) ** 2
		R = XYR[i][2] + XYR[j][2]
		return max(0, sqrt(tmp) - R)
	for i in range(N - 1):
		for j in range(i + 1, N):
			tmp = diff1(i, j)
			G[i].append((tmp, j))
			G[j].append((tmp, i))

	def diff2(x, y, i):
		tmp = (x - XYR[i][0]) ** 2 + (y - XYR[i][1]) ** 2
		R = XYR[i][2]
		return max(0, sqrt(tmp) - R)
	for i in range(N):
		tmp = diff2(xs, ys, i)
		G[N].append((tmp, i))
		G[i].append((tmp, N))
	for i in range(N):
		tmp = diff2(xg, yg, i)
		G[N + 1].append((tmp, i))
		G[i].append((tmp, N + 1))
	tmp = (xs - xg) ** 2 + (ys - yg) ** 2
	G[N].append((sqrt(tmp), N + 1))
	G[N + 1].append((sqrt(tmp), N))
	d = [INF] * (N + 2)

	def dijksrea(s):
		from heapq import heappop, heappush
		d[s] = 0
		pque = []
		heappush(pque, (0, s))
		while pque:
			p = heappop(pque)
			v = p[1]
			if d[v] < p[0]:
				continue
			for i in range(len(G[v])):
				e = G[v][i]
				if d[e[1]] > d[v] + e[0]:
					d[e[1]] = d[v] + e[0]
					heappush(pque, (d[e[1]], e[1]))
	dijksrea(N)
	print(d[N + 1])

def __starting_point():
	main()
__starting_point()


from heapq import heappush, heappop
(sx, sy, gx, gy) = map(int, input().split())
n = int(input())
g = [[] for i in range(n + 2)]
data = [(sx + sy * 1j, 0)]
for i in range(n):
	(a, b, c) = map(int, input().split())
	data.append((a + b * 1j, c))
data.append((gx + gy * 1j, 0))
for i in range(n + 2):
	for j in range(i + 1, n + 2):
		tmp = abs(data[i][0] - data[j][0]) - data[i][1] - data[j][1]
		g[i].append((tmp, j))
		g[j].append((tmp, i))
dist = [2828427127 for i in range(n + 2)]
visited = [False for i in range(n + 2)]
dist[0] = 0
que = []
heappush(que, (0, 0))
while que:
	(c, v) = heappop(que)
	if visited[v]:
		continue
	visited[v] = True
	for x in g[v]:
		if visited[x[1]]:
			continue
		tmp = x[0] + c if not x[0] < 0 else c
		if tmp < dist[x[1]]:
			dist[x[1]] = tmp
			heappush(que, (tmp, x[1]))
print(dist[n + 1])


(xs, ys, xt, yt) = map(int, input().split())
n = int(input())
X = [[0, 0, 0] for _ in range(n + 2)]
X[0] = [xs, ys, 0]
X[n + 1] = [xt, yt, 0]
R = [0] * n
for i in range(n):
	(x, y, r) = map(int, input().split())
	X[i + 1] = [x, y, r]
import math
edge = [[] for _ in range(n + 2)]
for i in range(n + 1):
	(x1, y1, r1) = X[i]
	for j in range(i + 1, n + 2):
		(x2, y2, r2) = X[j]
		l = math.sqrt((x1 - x2) ** 2 + (y1 - y2) ** 2)
		edge[i].append((max(l - r1 - r2, 0), j))
		edge[j].append((max(l - r1 - r2, 0), i))
import heapq

def dijkstra_heap(s):
	d = [float('inf')] * (n + 2)
	used = [True] * (n + 2)
	d[s] = 0
	used[s] = False
	edgelist = []
	for e in edge[s]:
		heapq.heappush(edgelist, e)
	while len(edgelist):
		minedge = heapq.heappop(edgelist)
		if not used[minedge[1]]:
			continue
		v = minedge[1]
		d[v] = minedge[0]
		used[v] = False
		for e in edge[v]:
			if used[e[1]]:
				heapq.heappush(edgelist, (e[0] + d[v], e[1]))
	return d
d = dijkstra_heap(0)
print(d[-1])


def main():
	from math import hypot
	import sys
	input = sys.stdin.readline
	inf = 1 << 60
	(xs, ys, xt, yt) = list(map(int, input().split()))
	N = int(input())
	N += 2

	def dist(p1, p2):
		d = hypot(p1[0] - p2[0], p1[1] - p2[1])
		return max(0, d - (p1[2] + p2[2]))
	s = (xs, ys, 0, 0)
	g = (xt, yt, 0, N - 1)
	ps = [s, g]
	adj = [[inf] * N for _ in range(N)]
	adj[0][N - 1] = adj[N - 1][0] = dist(s, g)
	for idx1 in range(1, N - 1):
		(*p1,) = list(map(int, input().split()))
		p1.append(idx1)
		for (*p2, idx2) in ps:
			d = dist(p1, p2)
			adj[idx1][idx2] = adj[idx2][idx1] = d
		ps.append(p1)

	def dijkstra(s):
		from heapq import heappop, heappush
		dist = [inf] * N
		h = [(0, s)]
		dist[s] = 0
		while h:
			(c, v) = heappop(h)
			if dist[v] < c:
				continue
			for (u, dc) in enumerate(adj[v]):
				nc = c + dc
				if dist[u] <= nc:
					continue
				dist[u] = nc
				heappush(h, (nc, u))
		return dist
	print(dijkstra(s=0)[N - 1])

def __starting_point():
	main()
__starting_point()


(xs, ys, xt, yt) = list(map(int, input().split()))
N = int(input())
XY = [tuple(map(int, input().split())) for i in range(N)]
D = [[0] * (N + 2) for i in range(N + 2)]
XY.append((xs, ys, 0))
XY.append((xt, yt, 0))
for i in range(N + 1):
	(x1, y1, r1) = XY[i]
	for j in range(i + 1, N + 2):
		(x2, y2, r2) = XY[j]
		d = (x1 - x2) ** 2 + (y1 - y2) ** 2
		d = d ** 0.5
		D[i][j] = max(0, d - r1 - r2)
		D[j][i] = D[i][j]
import heapq
hq = []
hq.append((0, N))
s = set([i for i in range(N + 2)])
while hq:
	(c, x) = heapq.heappop(hq)
	if x == N + 1:
		print(c)
		return
	if x in s:
		s.remove(x)
	else:
		continue
	for i in s:
		heapq.heappush(hq, (c + D[x][i], i))


printn = lambda x: print(x, end='')
inn = lambda : int(input())
inl = lambda : list(map(int, input().split()))
inm = lambda : map(int, input().split())
ins = lambda : input().strip()
DBG = True
BIG = 10 ** 18
R = 10 ** 9 + 7

def ddprint(x):
	if DBG:
		print(x)
from math import sqrt
from heapq import heappush, heappop

def pdist(x1, y1, x2, y2):
	return sqrt((x2 - x1) ** 2 + (y2 - y1) ** 2)
(xs, ys, xt, yt) = inm()
n = inn()
cir = []
for i in range(n):
	(x, y, r) = inm()
	cir.append((x, y, r))
dst = [[0] * (n + 2) for i in range(n + 2)]
dst[n][n + 1] = dst[n + 1][n] = pdist(xs, ys, xt, yt)
for i in range(n):
	(x, y, r) = cir[i]
	dst[n][i] = dst[i][n] = max(0.0, pdist(xs, ys, x, y) - r)
	dst[n + 1][i] = dst[i][n + 1] = max(0.0, pdist(xt, yt, x, y) - r)
	for j in range(i + 1, n):
		(xx, yy, rr) = cir[j]
		dst[j][i] = dst[i][j] = max(0.0, pdist(xx, yy, x, y) - rr - r)
if False and DBG:
	for i in range(n + 2):
		ddprint(dst[i])
cost = [float(BIG)] * (n + 2)
q = [(0.0, n)]
while len(q) > 0:
	(d, p) = heappop(q)
	if cost[p] <= d:
		continue
	cost[p] = d
	for v in range(n + 2):
		newdist = d + dst[p][v]
		if v != p and newdist < cost[v]:
			heappush(q, (newdist, v))
print(cost[n + 1])


import heapq
(xs, ys, xt, yt) = list(map(int, input().split()))
N = int(input())
XYR = [list(map(int, input().split())) for i in range(N)]
XYR.append([xs, ys, 0])
XYR.append([xt, yt, 0])
L = [[9999999999] * (N + 2) for i in range(N + 2)]
for i in range(N + 2):
	for j in range(i, N + 2):
		(x1, y1, r1) = XYR[i]
		(x2, y2, r2) = XYR[j]
		L[i][j] = L[j][i] = max(((x1 - x2) ** 2 + (y1 - y2) ** 2) ** 0.5 - r1 - r2, 0.0)
num = N + 2
start = num - 2
distance = [float('inf') for i in range(num)]
prev = [float('inf') for i in range(num)]
distance[start] = 0
q = []
heapq.heappush(q, (0, start))
while len(q) != 0:
	(prov_cost, src) = heapq.heappop(q)
	if distance[src] < prov_cost:
		continue
	for (destination, cost) in enumerate(L[src]):
		if distance[destination] > distance[src] + cost:
			distance[destination] = distance[src] + cost
			heapq.heappush(q, (distance[destination], destination))
			prev[destination] = src
print(distance[-1])


import heapq
import math
(xs, ys, xt, yt) = map(int, input().split())
N = int(input())
Coordinate = {-1: (xs, ys, 0), N: (xt, yt, 0)}
minRadiation = {int(i): 10 ** 20 for i in range(-1, N + 1)}
ToVisit = {int(i) for i in range(-1, N + 1)}
for i in range(N):
	(x, y, r) = map(int, input().split())
	Coordinate[i] = (x, y, r)
Q = [(0, -1)]
heapq.heapify(Q)
while Q:
	(nowRadiation, index) = heapq.heappop(Q)
	if index == N:
		print(nowRadiation)
		break
	elif index in ToVisit:
		ToVisit.difference_update({index})
		(nowx, nowy, nowr) = Coordinate[index]
		for nextIndex in ToVisit:
			(nextx, nexty, nextr) = Coordinate[nextIndex]
			tempTime = max(0, math.sqrt((nextx - nowx) ** 2 + (nexty - nowy) ** 2) - nowr - nextr) + nowRadiation
			if minRadiation[nextIndex] > tempTime:
				minRadiation[nextIndex] = tempTime
				heapq.heappush(Q, (tempTime, nextIndex))


(xs, ys, xt, yt) = map(int, input().split())
n = int(input())
p = [(xs, ys, 0), (xt, yt, 0)]
for i in range(n):
	p.append(tuple(map(int, input().split())))
edge = [[0] * (n + 2) for _ in range(n + 2)]
for i in range(n + 2):
	for j in range(i, n + 2):
		edge[i][j] = max(0, ((p[i][0] - p[j][0]) ** 2 + (p[i][1] - p[j][1]) ** 2) ** 0.5 - p[i][2] - p[j][2])
		edge[j][i] = max(0, ((p[i][0] - p[j][0]) ** 2 + (p[i][1] - p[j][1]) ** 2) ** 0.5 - p[i][2] - p[j][2])

def dijkstra(s, n, edges):
	INF = float('inf')
	d = [INF] * n
	d[s] = 0
	import heapq
	pq = [(0, s)]
	while len(pq):
		(c, v) = heapq.heappop(pq)
		if d[v] < c:
			continue
		for (nv, v2nvcost) in enumerate(edges[v]):
			if c + v2nvcost < d[nv]:
				d[nv] = c + v2nvcost
				heapq.heappush(pq, (d[nv], nv))
	return d
dist = dijkstra(0, n + 2, edge)
print(dist[1])


import sys
input = sys.stdin.readline
import heapq

def dijkstra(n, s, edges):
	hq = [(0, s)]
	cost = [float('inf')] * n
	cost[s] = 0
	while hq:
		(c, v) = heapq.heappop(hq)
		if c > cost[v]:
			continue
		for (d, u) in edges[v]:
			tmp = d + cost[v]
			if tmp < cost[u]:
				cost[u] = tmp
				heapq.heappush(hq, (tmp, u))
	return cost[-1]

def main():
	(xs, ys, xt, yt) = map(int, input().split())
	n = int(input())
	circles = []
	circles.append([xs, ys, 0])
	for _ in range(n):
		circles.append(list(map(int, input().split())))
	circles.append([xt, yt, 0])
	edges = [[] for _ in range(n + 2)]
	for i in range(n + 2):
		for j in range(i + 1, n + 2):
			dx = circles[i][0] - circles[j][0]
			dy = circles[i][1] - circles[j][1]
			d = (dx ** 2 + dy ** 2) ** 0.5
			r = circles[i][2] + circles[j][2]
			edges[i].append([max(0, d - r), j])
			edges[j].append([max(0, d - r), i])
	ans = dijkstra(n + 2, 0, edges)
	print(ans)
main()


from heapq import *
import sys
sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep='\n')

def II():
	return int(sys.stdin.readline())

def MI():
	return map(int, sys.stdin.readline().split())

def LI():
	return list(map(int, sys.stdin.readline().split()))

def LLI(rows_number):
	return [LI() for _ in range(rows_number)]

def SI():
	return sys.stdin.readline()[:-1]

def main():

	def cost(i, j):
		(x1, y1, r1) = xyr[i]
		(x2, y2, r2) = xyr[j]
		res = ((x1 - x2) ** 2 + (y1 - y2) ** 2) ** 0.5 - r1 - r2
		return max(res, 0)
	(sx, sy, gx, gy) = MI()
	n = II()
	xyr = LLI(n)
	xyr = [[sx, sy, 0]] + xyr + [[gx, gy, 0]]
	n += 2
	to = [[] for _ in range(n)]
	for i in range(n):
		(x1, y1, r1) = xyr[i]
		for j in range(i):
			(x2, y2, r2) = xyr[j]
			c = cost(i, j)
			to[i].append((j, c))
			to[j].append((i, c))
	hp = []
	fin = [False] * n
	heappush(hp, (0, 0))
	while hp:
		(d, u) = heappop(hp)
		if fin[u]:
			continue
		fin[u] = True
		if u == n - 1:
			print(d)
			exit()
		for (v, c) in to[u]:
			if fin[v]:
				continue
			heappush(hp, (d + c, v))
main()


from math import hypot

def dijkstra(s):
	d = [float('inf')] * n
	used = [False] * n
	d[s] = 0
	while True:
		v = -1
		for i in range(n):
			if not used[i] and v == -1:
				v = i
			elif not used[i] and d[i] < d[v]:
				v = i
		if v == -1:
			break
		used[v] = True
		for j in range(n):
			d[j] = min(d[j], d[v] + cost[v][j])
	return d
(sx, sy, gx, gy) = map(int, input().split())
n = int(input())
edge = [(sx, sy, 0)]
for i in range(n):
	(x, y, r) = map(int, input().split())
	edge.append((x, y, r))
edge.append((gx, gy, 0))
cost = [[0] * (n + 2) for _ in range(n + 2)]
for (j, (k1, k2, k3)) in enumerate(edge):
	for (l, (m1, m2, m3)) in enumerate(edge):
		if j == l:
			continue
		else:
			cost[j][l] = max(hypot(k1 - m1, k2 - m2) - k3 - m3, 0)
n += 2
res = dijkstra(0)
print(res[-1])


import sys
import heapq as h
stdin = sys.stdin
ni = lambda : int(ns())
nl = lambda : list(map(int, stdin.readline().split()))
nm = lambda : map(int, stdin.readline().split())
ns = lambda : stdin.readline().rstrip()

def dist(p, q):
	(px, py, pr) = p
	(qx, qy, qr) = q
	d = ((px - qx) ** 2 + (py - qy) ** 2) ** 0.5
	return max(d - (pr + qr), 0)
(xs, ys, xt, yt) = nm()
n = ni()
pl = [(xs, ys, 0)] + [tuple(nm()) for _ in range(n)] + [(xt, yt, 0)]
gr = [dict() for _ in range(n + 2)]
for i in range(n + 1):
	for j in range(i + 1, n + 2):
		gr[i][j] = dist(pl[i], pl[j])
		gr[j][i] = gr[i][j]
dis = [float('inf')] * (n + 2)
q = [(0, 0)]
while q:
	(d, v) = h.heappop(q)
	if dis[v] <= d:
		continue
	dis[v] = d
	for x in gr[v]:
		if dis[x] > dis[v] + gr[v][x]:
			h.heappush(q, (dis[v] + gr[v][x], x))
print(dis[-1])


import sys
from heapq import heappop, heappush

def I():
	return int(sys.stdin.readline().rstrip())

def MI():
	return list(map(int, sys.stdin.readline().rstrip().split()))
(xs, ys, xt, yt) = MI()
N = I()
XYR = []
for _ in range(N):
	XYR.append(tuple(MI()))
XYR.append((xs, ys, 0))
XYR.append((xt, yt, 0))
Graph = [[0] * (N + 2) for _ in range(N + 2)]
for i in range(N + 1):
	(x0, y0, r0) = XYR[i]
	for j in range(i + 1, N + 2):
		(x1, y1, r1) = XYR[j]
		Graph[i][j] = max(0, ((x1 - x0) ** 2 + (y1 - y0) ** 2) ** 0.5 - r0 - r1)
		Graph[j][i] = max(0, ((x1 - x0) ** 2 + (y1 - y0) ** 2) ** 0.5 - r0 - r1)
dist = [10 ** 10] * (N + 2)
dist[N] = 0
q = []
heappush(q, (0, N))
flag = [0] * (N + 2)
while q:
	(d, i) = heappop(q)
	if flag[i] == 1:
		continue
	flag[i] = 1
	for j in range(N + 2):
		if flag[j] == 0:
			new_d = d + Graph[i][j]
			if new_d < dist[j]:
				dist[j] = new_d
				heappush(q, (new_d, j))
print(dist[N + 1])


(Xs, Ys, Xt, Yt) = map(int, input().split())
n = int(input())
p = [(Xs, Ys, 0), (Xt, Yt, 0)]
for i in range(2, n + 2):
	p.append(tuple(map(int, input().split())))
cost = [[0] * (n + 2) for i in range(n + 2)]
for i in range(n + 2):
	for j in range(i, n + 2):
		cost[i][j] = cost[j][i] = max(((p[i][0] - p[j][0]) ** 2 + (p[i][1] - p[j][1]) ** 2) ** 0.5 - p[i][2] - p[j][2], 0)
n += 2
s = 0
d = [float('inf')] * n
used = [False] * n
d[s] = 0
while True:
	v = -1
	for i in range(n):
		if not used[i] and v == -1:
			v = i
		elif not used[i] and d[i] < d[v]:
			v = i
	if v == -1:
		break
	used[v] = True
	for j in range(n):
		d[j] = min(d[j], d[v] + cost[v][j])
print(d[1])


(start_x, start_y, goal_x, goal_y) = map(int, input().split())
n = int(input())
info = [(start_x, start_y, 0)] + [tuple(map(int, input().split())) for i in range(n)] + [(goal_x, goal_y, 0)]
graph = [[0] * (n + 2) for i in range(n + 2)]
for i in range(n + 2):
	for j in range(i, n + 2):
		diff_x = info[i][0] - info[j][0]
		diff_y = info[i][1] - info[j][1]
		sum_radius = info[i][2] + info[j][2]
		cost = max(0, (diff_x ** 2 + diff_y ** 2) ** 0.5 - sum_radius)
		graph[i][j] = cost
		graph[j][i] = cost
		graph = tuple(graph)
import heapq
distance = [float('inf')] * (n + 2)
used = [False] * (n + 2)
distance[0] = 0
while True:
	v = -1
	for u in range(n + 2):
		if not used[u] and (v == -1 or distance[u] < distance[v]):
			v = u
	if v == -1:
		break
	used[v] = True
	for u in range(n + 2):
		distance[u] = min(distance[u], distance[v] + graph[v][u])
print(distance[n + 1])


import heapq
(xs, ys, xt, yt) = list(map(int, input().split()))
N = int(input())
XYR = [(xs, ys, 0), (xt, yt, 0)]
for _ in range(N):
	XYR.append(tuple(map(int, input().split())))
D = [[0] * (N + 2) for _ in range(N + 2)]
for (i, (xi, yi, ri)) in enumerate(XYR):
	for (j, (xj, yj, rj)) in enumerate(XYR[:i]):
		dx = xj - xi
		dy = yj - yi
		d = (dx * dx + dy * dy) ** 0.5
		D[i][j] = D[j][i] = max(0, d - ri - rj)
Q = [(0, 0)]
dist = [-1] * (N + 2)
nvisited = 0
while nvisited < N + 2:
	(d, n) = heapq.heappop(Q)
	if dist[n] != -1:
		continue
	dist[n] = d
	nvisited += 1
	for (e, d_ne) in enumerate(D[n]):
		if dist[e] == -1:
			heapq.heappush(Q, (d + d_ne, e))
print(dist[1])


from heapq import heappush, heappop
INF = 10 ** 10

def dijkstra(N, G, s):
	dist = [INF] * N
	que = [(0, s)]
	dist[s] = 0
	while que:
		(c, v) = heappop(que)
		if dist[v] < c:
			continue
		for (t, cost) in enumerate(G[v]):
			if dist[v] + cost < dist[t]:
				dist[t] = dist[v] + cost
				heappush(que, (dist[t], t))
	return dist
(xs, ys, xt, yt) = map(int, input().split())
n = int(input())
p = [(xs, ys, 0)] + [tuple(map(int, input().split())) for _ in range(n)] + [(xt, yt, 0)]

def d(pj, pk):
	dis = (pj[0] - pk[0]) ** 2 + (pj[1] - pk[1]) ** 2
	return max(dis ** (1 / 2) - pk[2] - pj[2], 0)
D = [[d(p[i], p[j]) for i in range(n + 2)] for j in range(n + 2)]
ans = dijkstra(n + 2, D, 0)
print(ans[-1])


import sys
import heapq
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)

def dist(x1, y1, x2, y2):
	dx = x1 - x2
	dy = y1 - y2
	return (dx ** 2 + dy ** 2) ** 0.5
(xs, ys, xg, yg) = map(int, input().split())
N = int(input())
XYR = [tuple(map(int, input().split())) for _ in range(N)]
edge = [[] for _ in range(N + 2)]
for i in range(N - 1):
	(xi, yi, ri) = XYR[i]
	for j in range(i + 1, N):
		(xj, yj, rj) = XYR[j]
		d = max(0, dist(xi, yi, xj, yj) - ri - rj)
		edge[i].append((j, d))
		edge[j].append((i, d))
for i in range(N):
	(xi, yi, ri) = XYR[i]
	ds = max(0, dist(xi, yi, xs, ys) - ri)
	edge[i].append((N, ds))
	edge[N].append((i, ds))
	dg = max(0, dist(xi, yi, xg, yg) - ri)
	edge[i].append((N + 1, dg))
	edge[N + 1].append((i, dg))
d = dist(xs, ys, xg, yg)
edge[N].append((N + 1, d))
edge[N + 1].append((N, d))
inf = 10 ** 18
dist = [inf] * (N + 10)
dist[N] = 0
que = [(0, N)]
while que:
	(c, s) = heapq.heappop(que)
	if dist[s] < c:
		continue
	for (t, cost) in edge[s]:
		if dist[t] > dist[s] + cost:
			dist[t] = dist[s] + cost
			heapq.heappush(que, (dist[t], t))
print(dist[N + 1])


from collections import defaultdict
(xs, ys, xt, yt) = map(int, input().split())
P = []
inf = float('inf')
P.append((xs, ys, 0))
P.append((xt, yt, 0))
N = int(input())
for i in range(N):
	(x, y, r) = map(int, input().split())
	P.append((x, y, r))
G = defaultdict(int)
for i in range(N + 2):
	for j in range(N + 2):
		(x1, y1, r1, x2, y2, r2) = (P[i][0], P[i][1], P[i][2], P[j][0], P[j][1], P[j][2])
		d = ((x1 - x2) ** 2 + (y1 - y2) ** 2) ** (1 / 2)
		G[i, j] = max(0, d - r1 - r2)

def dijkstra():
	d = [inf] * (N + 2)
	d[0] = 0
	used = [False] * (N + 2)
	while True:
		v = -1
		for i in range(N + 2):
			if used[i] == False and (v == -1 or d[i] < d[v]):
				v = i
		if v == -1:
			break
		used[v] = True
		for j in range(N + 2):
			d[j] = min(d[j], d[v] + G[v, j])
	return d[1]
print(dijkstra())


import sys
import heapq
my_input = sys.stdin.readline

def main():
	(xs, ys, xt, yt) = map(int, my_input().split())
	N = int(my_input())
	C = [(xs, ys, 0), (xt, yt, 0)]
	C += [tuple(map(int, my_input().split())) for i in range(N)]
	G = [[] for i in range(N + 2)]
	for i in range(N + 2):
		for j in range(i + 1, N + 2):
			cost = max(0, ((C[i][0] - C[j][0]) ** 2 + (C[i][1] - C[j][1]) ** 2) ** 0.5 - (C[i][2] + C[j][2]))
			G[i].append((j, cost))
			G[j].append((i, cost))

	def dijkstra(graph, start, inf=float('inf')):
		import heapq
		n = len(graph)
		distances = [inf] * n
		distances[start] = 0
		visited = [False] * n
		hq = [(0, start)]
		while hq:
			(dist, fr) = heapq.heappop(hq)
			visited[fr] = True
			if distances[fr] < dist:
				continue
			if fr == 1:
				return distances
			for (to, cost) in graph[fr]:
				new_dist = distances[fr] + cost
				if visited[to] or distances[to] <= new_dist:
					continue
				distances[to] = new_dist
				heapq.heappush(hq, (new_dist, to))
		return distances
	dist = dijkstra(G, 0)
	print(dist[1])
main()


from heapq import heappop, heappush
from math import sqrt

def distf(xyr, i, j):
	(x, y, r) = xyr[i]
	(x1, y1, r1) = xyr[j]
	d = max(0, sqrt((x - x1) ** 2 + (y - y1) ** 2) - r - r1)
	return d

def main():
	(xs, ys, xt, yt) = map(int, input().split())
	n = int(input())
	xyr = [list(map(int, input().split())) for _ in range(n)]
	xyr.append([xs, ys, 0])
	xyr.append([xt, yt, 0])
	inf = float('inf')
	dist = [[inf] * (n + 2) for _ in range(n + 2)]
	for i in range(n + 2):
		dist[i][i] = 0
	for i in range(n + 1):
		for j in range(i + 1, n + 2):
			dist[i][j] = distf(xyr, i, j)
			dist[j][i] = dist[i][j]
	seen = [inf] * (n + 2)
	seen[n] = 0
	mi = set(range(n + 2))
	while mi:
		(d, v) = (inf, -1)
		for j in mi:
			if d > seen[j]:
				d = seen[j]
				v = j
		mi.remove(v)
		for nv in mi:
			nd = dist[v][nv]
			if seen[nv] > seen[v] + nd:
				seen[nv] = seen[v] + nd
	print(seen[n + 1])
main()


from math import sqrt
(xs, ys, xt, yt) = map(int, input().split())
n = int(input())
xyr = [list(map(int, input().split())) for i in range(n)]
xyr.insert(0, [xs, ys, 0])
xyr.append([xt, yt, 0])
Graph = [[0] * (n + 2) for i in range(n + 2)]
for i in range(n + 2):
	for j in range(n + 2):
		Graph[i][j] = max(0, sqrt((xyr[i][0] - xyr[j][0]) ** 2 + (xyr[i][1] - xyr[j][1]) ** 2) - (xyr[i][2] + xyr[j][2]))
INF = 10 ** 18
dist = [INF] * (n + 2)
visited = [False] * (n + 2)
dist[0] = 0
while True:
	v = -1
	for i in range(n + 2):
		if not visited[i] and (v == -1 or dist[i] < dist[v]):
			v = i
	if v == -1:
		break
	visited[v] = True
	for i in range(n + 2):
		dist[i] = min(dist[i], dist[v] + Graph[v][i])
print(dist[-1])


import sys
sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7

def resolve():
	(xs, ys, xt, yt) = map(int, input().split())
	n = int(input())
	XYR = [[xs, ys, 0], [xt, yt, 0]]
	for _ in range(n):
		(x, y, r) = map(int, input().split())
		XYR.append([x, y, r])
	cost = [[0] * (n + 2) for _ in range(n + 2)]
	for i in range(n + 2):
		(x1, y1, r1) = XYR[i]
		for j in range(n + 2):
			(x2, y2, r2) = XYR[j]
			dist = max(0, pow(pow(x1 - x2, 2) + pow(y1 - y2, 2), 0.5) - (r1 + r2))
			cost[i][j] = cost[j][i] = dist

	def dijkstra(s):
		d = [f_inf] * (n + 2)
		used = [False] * (n + 2)
		d[s] = 0
		while True:
			v = -1
			for k in range(n + 2):
				if not used[k] and v == -1:
					v = k
				elif not used[k] and d[k] < d[v]:
					v = k
			if v == -1:
				break
			used[v] = True
			for m in range(n + 2):
				d[m] = min(d[m], d[v] + cost[v][m])
		return d
	res = dijkstra(0)
	print(res[1])
resolve()


import math
(xs, ys, xt, yt) = map(int, input().split())
N = int(input())
xyrlist = []
for _ in range(N):
	(x, y, r) = map(int, input().split())
	xyrlist.append((x, y, r))
graph = [[] for _ in range(N + 2)]
graph[0].append((N + 1, math.sqrt((xt - xs) ** 2 + (yt - ys) ** 2)))
for i in range(N):
	(xi, yi, ri) = xyrlist[i]
	if (xs - xi) ** 2 + (ys - yi) ** 2 <= ri ** 2:
		graph[0].append((i + 1, 0))
	else:
		graph[0].append((i + 1, math.sqrt((xs - xi) ** 2 + (ys - yi) ** 2) - ri))
for i in range(N):
	(xi, yi, ri) = xyrlist[i]
	for j in range(i + 1, N):
		(xj, yj, rj) = xyrlist[j]
		if (xj - xi) ** 2 + (yj - yi) ** 2 <= (ri + rj) ** 2:
			graph[i + 1].append((j + 1, 0))
			graph[j + 1].append((i + 1, 0))
		else:
			graph[i + 1].append((j + 1, math.sqrt((xj - xi) ** 2 + (yj - yi) ** 2) - ri - rj))
			graph[j + 1].append((i + 1, math.sqrt((xj - xi) ** 2 + (yj - yi) ** 2) - ri - rj))
for i in range(N):
	(xi, yi, ri) = xyrlist[i]
	if (xt - xi) ** 2 + (yt - yi) ** 2 <= ri ** 2:
		graph[i + 1].append((N + 1, 0))
	else:
		graph[i + 1].append((N + 1, math.sqrt((xt - xi) ** 2 + (yt - yi) ** 2) - ri))
import heapq

def dijkstra_heap(s):
	dist = [float('inf')] * size_v
	used = [False] * size_v
	dist[s] = 0
	used[s] = True
	hq_edge = []
	for (v, w) in graph[s]:
		heapq.heappush(hq_edge, (w, v))
	while hq_edge:
		(min_w, min_v) = heapq.heappop(hq_edge)
		if used[min_v]:
			continue
		dist[min_v] = min_w
		used[min_v] = True
		for (v, w) in graph[min_v]:
			if not used[v]:
				heapq.heappush(hq_edge, (min_w + w, v))
	return dist
size_v = N + 2
dist = dijkstra_heap(0)
print(dist[N + 1])


from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra
(xs, ys, xt, yt) = map(int, input().split())
N = int(input())
xyr = [list(map(int, input().split())) for i in range(N)]

def dist(x1, y1, x2, y2):
	return ((x1 - x2) ** 2 + (y1 - y2) ** 2) ** 0.5
row = [0]
col = [1]
data = [dist(xs, ys, xt, yt)]
for (i, (xi, yi, ri)) in enumerate(xyr, 2):
	d1 = max(0, dist(xi, yi, xs, ys) - ri)
	d2 = max(0, dist(xi, yi, xt, yt) - ri)
	row.extend([0, 1])
	col.extend([i, i])
	data.extend([d1, d2])
	for j in range(i - 1, N):
		(xj, yj, rj) = xyr[j]
		dij = max(0, dist(xi, yi, xj, yj) - ri - rj)
		row.append(i)
		col.append(j + 2)
		data.append(dij)
graph = csr_matrix((data, (row, col)), shape=(N + 2, N + 2))
dist = dijkstra(graph, directed=False, indices=0)
print(dist[1])


import sys, bisect, string, math, time, functools, random
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
from itertools import permutations, combinations, groupby

def Golf():
	(*a,) = map(int, open(0))

def I():
	return int(input())

def S_():
	return input()

def IS():
	return input().split()

def LS():
	return [i for i in input().split()]

def LI():
	return [int(i) for i in input().split()]

def LI_():
	return [int(i) - 1 for i in input().split()]

def NI(n):
	return [int(input()) for i in range(n)]

def NI_(n):
	return [int(input()) - 1 for i in range(n)]

def StoLI():
	return [ord(i) - 97 for i in input()]

def ItoS(n):
	return chr(n + 97)

def LtoS(ls):
	return ''.join([chr(i + 97) for i in ls])

def GI(V, E, ls=None, Directed=False, index=1):
	org_inp = []
	g = [[] for i in range(V)]
	FromStdin = True if ls == None else False
	for i in range(E):
		if FromStdin:
			inp = LI()
			(a, b, c) = (inp + [1])[:3]
			org_inp.append(inp)
		else:
			(a, b, c) = (list(ls[i]) + [1])[:3]
		if index == 1:
			a -= 1
			b -= 1
		aa = (a, c)
		bb = (b, c)
		g[a].append(bb)
		if not Directed:
			g[b].append(aa)
	return (g, org_inp)

def GGI(h, w, search=None, replacement_of_found='.', mp_def={'#': 1, '.': 0}):
	mp = [1] * (w + 2)
	found = {}
	for i in range(h):
		s = input()
		for char in search:
			if char in s:
				found[char] = (i + 1) * (w + 2) + s.index(char) + 1
				mp_def[char] = mp_def[replacement_of_found]
		mp += [1] + [mp_def[j] for j in s] + [1]
	mp += [1] * (w + 2)
	return (h + 2, w + 2, mp, found)

def TI(n):
	return GI(n, n - 1)

def bit_combination(k, n=2):
	rt = []
	for tb in range(n ** k):
		s = [tb // n ** bt % n for bt in range(k)]
		rt += [s]
	return rt

def show(*inp, end='\n'):
	if show_flg:
		print(*inp, end=end)
YN = ['YES', 'NO']
Yn = ['Yes', 'No']
mo = 10 ** 9 + 7
inf = float('inf')
l_alp = string.ascii_lowercase
input = lambda : sys.stdin.readline().rstrip()

class Comb:

	def __init__(self, n, mo=10 ** 9 + 7):
		self.fac = [0] * (n + 1)
		self.inv = [1] * (n + 1)
		self.fac[0] = 1
		self.fact(n)
		for i in range(1, n + 1):
			self.fac[i] = i * self.fac[i - 1] % mo
			self.inv[n] *= i
			self.inv[n] %= mo
		self.inv[n] = pow(self.inv[n], mo - 2, mo)
		for i in range(1, n):
			self.inv[n - i] = self.inv[n - i + 1] * (n - i + 1) % mo
		return

	def fact(self, n):
		return self.fac[n]

	def invf(self, n):
		return self.inv[n]

	def comb(self, x, y):
		if y < 0 or y > x:
			return 0
		return self.fac[x] * self.inv[x - y] * self.inv[y] % mo
show_flg = False
show_flg = True

class Tree:

	def __init__(self, inp_size=None, init=True):
		if init:
			self.stdin(inp_size)
		return

	def stdin(self, inp_size=None):
		if inp_size == None:
			self.size = int(input())
		else:
			self.size = inp_size
		(self.edges, _) = GI(self.size, self.size - 1)
		return

	def listin(self, ls):
		self.size = len(ls) + 1
		(self.edges, _) = GI(self.size, self.size - 1, ls)
		return

	def __str__(self):
		return str(self.edges)

	def dfs(self, x, func=lambda prv, nx, dist: prv + dist, root_v=0):
		q = deque()
		q.append(x)
		v = [-1] * self.size
		v[x] = root_v
		while q:
			c = q.pop()
			for (nb, d) in self.edges[c]:
				if v[nb] == -1:
					q.append(nb)
					v[nb] = func(v[c], nb, d)
		return v

	def EulerTour(self, x, func=lambda prv, nx, dist: prv + dist, root_v=0):
		q = deque()
		q.append((-1, x))
		v = [None] * self.size
		v[x] = root_v
		et = []
		while q:
			(cb, ce) = q.pop()
			et.append(ce)
			for (nb, d) in self.edges[ce]:
				if v[nb] == None:
					q.append((nb, ce))
					q.append((ce, nb))
					v[nb] = func(v[ce], nb, d)
		vid = [[-1, -1] for i in range(self.size)]
		for (i, j) in enumerate(et):
			if vid[j][0] == -1:
				vid[j][0] = i
			else:
				vid[j][1] = i
		return (v, et, vid)

	def LCA_init(self, depth, et):
		self.st = SegTree(self.size * 2 - 1, func=min, ide=inf)
		for (i, j) in enumerate(et):
			self.st.update(i, j)
		self.LCA_init_stat == True
		return

	def LCA(self, root, x, y):
		if self.LCA_init_stat == False:
			(depth, et, vid) = self.EulerTour(root)
			self.LCA_init(depth, et)
		return self.st.query(x, y + 1)

def dijkstra(edge, st):
	n = len(edge)
	d = [0 if st == i else 1 << 33 for i in range(n)]
	prev = [0] * n
	q = [(j, i) for (i, j) in enumerate(d)]
	heapify(q)
	remain = set(range(n))
	while q:
		(dist, cur) = heappop(q)
		if cur not in remain:
			continue
		remain.remove(cur)
		for (dst, dist) in edge[cur]:
			alt = d[cur] + dist
			if alt < d[dst]:
				d[dst] = alt
				prev[dst] = cur
				heappush(q, (alt, dst))
	return (d, prev)
(sx, sy, gx, gy) = LI()
n = I()
c = [(sx, sy, 0), (gx, gy, 0)]
for i in range(n):
	c += [LI()]
n += 2
g = [[] for i in range(n)]
for i in range(n):
	for j in range(i + 1, n):
		(x, y, r1) = c[i]
		(s, t, r2) = c[j]
		d = math.hypot(x - s, y - t) - r1 - r2
		if d < 0:
			d = 0
		g[i].append((j, d))
		g[j].append((i, d))
(d, _) = dijkstra(g, 0)
print(d[1])


from scipy.sparse.csgraph import csgraph_from_dense, dijkstra
import numpy as np
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

def main():
	(x_s, y_s, x_t, y_t) = list(map(int, readline().split()))
	A = np.array([[x_s, y_s, 0], [x_t, y_t, 0]], dtype=np.int)
	N = int(readline())
	B = np.array(read().split(), dtype=np.int).reshape(-1, 3)
	(XY, R) = np.hsplit(np.concatenate((A, B)), [2])
	d = np.expand_dims(XY, axis=1) - np.expand_dims(XY, axis=0)
	d = np.sqrt(np.sum(np.square(d), axis=-1))
	d -= R + R.reshape(1, -1)
	d = np.maximum(d, 0)
	np.fill_diagonal(d, -1)
	d = csgraph_from_dense(d, null_value=-1)
	ans = dijkstra(d, indices=0)[1]
	print(ans)

def __starting_point():
	main()
__starting_point()


import sys
sys.setrecursionlimit(2147483647)
INF = float('inf')
MOD = 10 ** 9 + 7
input = lambda : sys.stdin.readline().rstrip()
from itertools import product

def resolve():
	(xs, ys, xt, yt) = map(int, input().split())
	n = int(input())
	CR = [None] * (n + 2)
	CR[0] = (xs + ys * 1j, 0)
	CR[n + 1] = (xt + yt * 1j, 0)
	for i in range(1, n + 1):
		(x, y, r) = map(int, input().split())
		CR[i] = (x + y * 1j, r)
	n += 2
	E = [[] for _ in range(n)]
	for (i, j) in product(range(n), repeat=2):
		if i >= j:
			continue
		(c0, r0) = CR[i]
		(c1, r1) = CR[j]
		d = max(0, abs(c0 - c1) - r0 - r1)
		E[i].append((j, d))
		E[j].append((i, d))
	dist = [INF] * n
	dist[0] = 0
	used = [0] * n
	for _ in range(n - 1):
		v = min(((dist[v], v) for v in range(n) if not used[v]))[1]
		used[v] = 1
		for (nv, w) in E[v]:
			if dist[nv] > dist[v] + w:
				dist[nv] = dist[v] + w
	print(dist[-1])
resolve()


import math
(xs, ys, xg, yg) = map(int, input().split())
n = int(input())
c = [[-1, xs, ys, 0]]
for i in range(n):
	(x, y, r) = map(int, input().split())
	c.append([max(math.sqrt(abs(xs - x) ** 2 + abs(ys - y) ** 2) - r, 0), x, y, r])
dp = [float('inf')] * (n + 1)
dp[0] = 0
used = [0] * (n + 1)
for i in range(n + 1):
	a = float('inf')
	b = -1
	for j in range(n + 1):
		if used[j]:
			continue
		if a > dp[j]:
			a = dp[j]
			b = j
	used[b] = 1
	g = b
	(_, x, y, r) = c[b]
	for j in range(n + 1):
		if used[j]:
			continue
		(_, x2, y2, r2) = c[j]
		ima = dp[g] + max(0, math.sqrt(abs(x2 - x) ** 2 + abs(y2 - y) ** 2) - r - r2)
		if ima < dp[j]:
			dp[j] = ima
ans = float('inf')
for i in range(n + 1):
	(_, x, y, r) = c[i]
	ans = min(dp[i] + max(0, math.sqrt(abs(xg - x) ** 2 + abs(yg - y) ** 2) - r), ans)
print(ans)


def resolve():
	import sys
	input = sys.stdin.readline
	import heapq

	def dijkstra_heap(s, g, edge):
		d = [10 ** 20] * (n + 2)
		used = [True] * (n + 2)
		d[s] = 0
		used[s] = False
		edgelist = []
		(sx, sy, sr) = (edge[s][0], edge[s][1], edge[s][2])
		for i in range(n + 2):
			(x, y, r) = (edge[i][0], edge[i][1], edge[i][2])
			dist = ((x - sx) ** 2 + (y - sy) ** 2) ** (1 / 2)
			heapq.heappush(edgelist, (max(dist - r - sr, 0), i))
		while len(edgelist):
			minedge = heapq.heappop(edgelist)
			v = minedge[1]
			if not used[v]:
				continue
			d[v] = minedge[0]
			used[v] = False
			(bx, by, br) = (edge[v][0], edge[v][1], edge[v][2])
			for i in range(n + 2):
				(x, y, r) = (edge[i][0], edge[i][1], edge[i][2])
				dist = ((x - bx) ** 2 + (y - by) ** 2) ** (1 / 2)
				if used[i]:
					heapq.heappush(edgelist, (max(dist - r - br, 0) + d[v], i))
			if not used[g]:
				break
		return d[g]
	(sx, sy, gx, gy) = map(int, input().split())
	n = int(input())
	edge = [(sx, sy, 0), (gx, gy, 0)]
	for i in range(2, n + 2):
		(x, y, r) = map(int, input().split())
		edge.append((x, y, r))
	print(dijkstra_heap(0, 1, edge))
resolve()


import sys
input = sys.stdin.readline
from heapq import heappush, heappop

def dijkstra(x, Route):
	n = len(Route)
	D = [float('inf')] * n
	D[x] = 0
	hq = [(0, x)]
	while hq:
		(c, u) = heappop(hq)
		if D[u] < c:
			continue
		for (v, cost) in Route[u]:
			if D[u] + cost < D[v]:
				D[v] = D[u] + cost
				heappush(hq, (D[v], v))
	return D

def dist(V1, V2):
	return max(0, ((V2[0] - V1[0]) ** 2 + (V2[1] - V1[1]) ** 2) ** 0.5 - (V1[2] + V2[2]))
(sx, sy, gx, gy) = map(int, input().split())
n = int(input())
V = [(sx, sy, 0)] + [tuple(map(int, input().split())) for _ in range(n)] + [(gx, gy, 0)]
Edges = [[] for _ in range(n + 2)]
for i in range(n + 1):
	for j in range(i + 1, n + 2):
		d = dist(V[i], V[j])
		Edges[i].append((j, d))
		Edges[j].append((i, d))
print(dijkstra(0, Edges)[-1])


from heapq import heappush, heappop
(sX, sY, tX, tY) = list(map(int, input().split()))
N = int(input())
XYR = [tuple(map(int, input().split())) for _ in range(N)] + [(sX, sY, 0), (tX, tY, 0)]
(S, T) = (N, N + 1)
N += 2
edges = [[] for _ in range(N)]
for (i, (x, y, r)) in enumerate(XYR):
	for (j, (u, v, w)) in enumerate(XYR[i + 1:], start=i + 1):
		dist = max(0, ((x - u) ** 2 + (y - v) ** 2) ** 0.5 - (r + w))
		edges[i].append((j, dist))
		edges[j].append((i, dist))
minDist = [10 ** 18] * N
minDist[S] = 0
que = [(0, S)]
while que:
	(dist, now) = heappop(que)
	if minDist[now] < dist:
		continue
	for (to, cost) in edges[now]:
		d = dist + cost
		if minDist[to] > d:
			minDist[to] = d
			heappush(que, (d, to))
print(minDist[T])


from itertools import combinations
from heapq import heappush, heappop

class Dijkstra:

	def __init__(self, N):
		self.N = N
		self.E = [[] for _ in range(N)]

	def add_edge(self, init, end, weight, undirected=False):
		self.E[init].append((end, weight))
		if undirected:
			self.E[end].append((init, weight))

	def distance(self, s):
		INF = float('inf')
		(E, N) = (self.E, self.N)
		self.dist = dist = [INF] * N
		self.prev = prev = [-1] * N
		dist[s] = 0
		n_visited = 0
		heap = []
		heappush(heap, (0, s))
		while heap:
			(d, v) = heappop(heap)
			if dist[v] < d:
				continue
			for (u, c) in E[v]:
				temp = d + c
				if dist[u] > temp:
					dist[u] = temp
					prev[u] = v
					heappush(heap, (temp, u))
			n_visited += 1
			if n_visited == N:
				break
		return dist

	def shortest_path(self, t):
		P = []
		prev = self.prev
		while True:
			P.append(t)
			t = prev[t]
			if t == -1:
				break
		return P[::-1]

def dist(p1, p2):
	return ((p1[0] - p2[0]) ** 2 + (p1[1] - p2[1]) ** 2) ** 0.5
(xs, ys, xt, yt) = map(int, input().split())
N = int(input())
P = [[(xs, ys), 0, 0], [(xt, yt), 0, 1]]
for i in range(2, N + 2):
	(x, y, r) = map(int, input().split())
	P.append([(x, y), r, i])
dk = Dijkstra(N + 2)
for ([p1, r1, i], [p2, r2, j]) in combinations(P, 2):
	d = max(0, dist(p1, p2) - (r1 + r2))
	dk.add_edge(i, j, d, undirected=True)
print(dk.distance(0)[1])


import math
import heapq as hp
import sys
input = sys.stdin.readline
(sx, sy, tx, ty) = map(int, input().split())
N = int(input())
XYR = [list(map(int, input().split())) for _ in range(N)]
INF = 10 ** 14
graph = [[] for _ in range(N + 2)]
for i in range(N - 1):
	for j in range(1, N):
		(x1, y1, r1) = XYR[i]
		(x2, y2, r2) = XYR[j]
		d = max(0, math.sqrt((x1 - x2) ** 2 + (y1 - y2) ** 2) - r1 - r2)
		graph[i].append((d, j))
		graph[j].append((d, i))
for i in range(N):
	(x, y, r) = XYR[i]
	graph[N].append((max(0, math.sqrt((x - sx) ** 2 + (y - sy) ** 2) - r), i))
	graph[i].append((max(0, math.sqrt((x - tx) ** 2 + (y - ty) ** 2) - r), N + 1))
graph[N].append((math.sqrt((tx - sx) ** 2 + (ty - sy) ** 2), N + 1))
D = [INF for _ in range(N + 2)]
D[N] = 0
q = []
hp.heappush(q, (0, N))
while q:
	(nd, np) = hp.heappop(q)
	if D[np] < nd:
		continue
	for (d, p) in graph[np]:
		if D[p] > D[np] + d:
			D[p] = D[np] + d
			hp.heappush(q, (D[p], p))
print(D[N + 1])


from collections import defaultdict
import heapq
from math import sqrt
import sys
sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline

def calc(b1, b2):
	(x1, y1, r1) = b1
	(x2, y2, r2) = b2
	d = sqrt((x1 - x2) ** 2 + (y1 - y2) ** 2)
	return max(d - (r1 + r2), 0)
(sx, sy, gx, gy) = map(int, input().split())
N = int(input())
barriers = [[sx, sy, 0]] + [list(map(int, input().split())) for _ in range(N)] + [[gx, gy, 0]]
mat = [[0] * (N + 2) for _ in range(N + 2)]
for row in range(N + 2):
	for col in range(row + 1, N + 2):
		d = calc(barriers[row], barriers[col])
		mat[row][col] = d
		mat[col][row] = d
dist = [float('inf')] * (N + 2)
dist[0] = 0
prev = defaultdict(lambda : None)
Q = []
heapq.heappush(Q, (0, 0))
while Q:
	(dist_to_node, node) = heapq.heappop(Q)
	if dist[node] < dist_to_node:
		continue
	else:
		for v in range(N + 2):
			weight = mat[node][v]
			alt = dist_to_node + weight
			if dist[v] > alt:
				dist[v] = alt
				prev[v] = node
				heapq.heappush(Q, (alt, v))
print(dist[-1])


from heapq import *

def Dijkstra(G: list, source=0):
	INF = float('inf')
	V = len(G)
	D = [INF] * V
	D[source] = 0
	vis = [False] * V
	H = [(0, source)]
	while H:
		(dist, cur) = heappop(H)
		if vis[cur]:
			continue
		vis[cur] = True
		for (nxt, cost) in G[cur]:
			t = dist + cost
			if D[nxt] > t:
				D[nxt] = t
				heappush(H, (t, nxt))
	return D
import sys
input = sys.stdin.buffer.readline
from math import hypot
(sx, sy, gx, gy) = map(int, input().split())
n = int(input())
v = [(sx, sy, 0), (gx, gy, 0)]
for _ in range(n):
	v.append(tuple(map(int, input().split())))
con = [[] for _ in range(n + 2)]
for (i, p1) in enumerate(v):
	for (j, p2) in enumerate(v[i + 1:]):
		t = max(0, hypot(p1[0] - p2[0], p1[1] - p2[1]) - p1[2] - p2[2])
		con[i].append((i + j + 1, t))
		con[i + j + 1].append((i, t))
print(Dijkstra(con)[1])


from heapq import heappush, heappop
(xs, ys, xt, yt) = map(int, input().split())
n = int(input())
XY = [list(map(int, input().split())) for i in range(n)]
XY.append([xs, ys, 0])
XY.append([xt, yt, 0])
inf = 10 ** 14
e = [[inf] * (n + 2) for i in range(n + 2)]
for i in range(n + 1):
	for j in range(i + 1, n + 2):
		(xi, yi, ri) = XY[i]
		(xj, yj, rj) = XY[j]
		dif = max(0.0, ((xi - xj) ** 2 + (yi - yj) ** 2) ** 0.5 - ri - rj)
		e[i][j] = e[j][i] = dif
h = []
heappush(h, (0, n))
dis = [inf] * (n + 2)
dis[n] = 0
while h:
	(cost, now) = heappop(h)
	if cost > dis[now]:
		continue
	for (nex, dif) in enumerate(e[now]):
		if dis[nex] > dis[now] + dif:
			dis[nex] = dis[now] + dif
			heappush(h, (dis[nex], nex))
print(dis[-1])


import math
(x1, y1, x2, y2) = [int(i) for i in input().split()]
n = int(input())
xy = [[x1, y1, 0]]
for _ in range(n):
	xy.append([int(i) for i in input().split()])
xy.append([x2, y2, 0])

def dif(x, y):
	return max(0, math.sqrt((x[0] - y[0]) ** 2 + (x[1] - y[1]) ** 2) - x[2] - y[2])
q = set([i for i in range(n + 2)])
mi = [10 ** 16] * (n + 2)
mi[0] = 0
while q:
	u = -1
	mm = 10 ** 16
	for i in q:
		if mm > mi[i]:
			mm = mi[i]
			u = i
	q.remove(u)
	for i in q:
		mi[i] = min(mi[i], mi[u] + dif(xy[i], xy[u]))
print(mi[-1])


(sx, sy, gx, gy) = list(map(int, input().split()))
N = int(input())
zone = [list(map(int, input().split())) for i in range(N)]
zone = [[sx, sy, 0]] + zone + [[gx, gy, 0]]
G = [[0] * (N + 2) for i in range(N + 2)]
for i in range(len(zone) - 1):
	for j in range(i + 1, len(zone)):
		dist = ((zone[i][0] - zone[j][0]) ** 2 + (zone[i][1] - zone[j][1]) ** 2) ** 0.5
		dist = max(0, dist - (zone[i][2] + zone[j][2]))
		G[i][j] = dist
		G[j][i] = dist
import heapq as hq
q = [(0, 0)]
hq.heapify(q)
seen = set()
while q:
	(dist, v) = hq.heappop(q)
	if v in seen:
		continue
	seen.add(v)
	if v == N + 1:
		print(dist)
		break
	for i in range(len(G[v])):
		if i in seen:
			continue
		hq.heappush(q, (dist + G[v][i], i))


import math
import heapq
(xs, ys, xt, yt) = map(int, input().split())
N = int(input())
d = [((xs, ys), 0, 0)]
for _ in range(N):
	(x, y, r) = map(int, input().split())
	d.append(((x, y), _ + 1, r))
graph = {i: [] for i in range(N + 2)}
d.append(((xt, yt), N + 1, 0))
for i in range(N + 2):
	for j in range(i + 1, N + 2):
		(p, point, rad) = d[i]
		(q, point2, rad2) = d[j]
		D = math.hypot(p[0] - q[0], p[1] - q[1])
		if D > rad + rad2:
			graph[i].append((D - rad - rad2, j))
			graph[j].append((D - rad - rad2, i))
		else:
			graph[i].append((0, j))
			graph[j].append((0, i))

def dijkstra(s, graph):
	n = len(graph)
	dist = [float('inf') for i in range(n + 1)]
	dist[s] = 0
	pq = []
	heapq.heapify(pq)
	heapq.heappush(pq, (0, s))
	while pq:
		(mini_dis, node) = heapq.heappop(pq)
		if dist[node] < mini_dis:
			continue
		for (w, point) in graph[node]:
			if dist[point] < w:
				continue
			newlen = dist[node] + w
			if newlen < dist[point]:
				heapq.heappush(pq, (newlen, point))
				dist[point] = newlen
	return dist
K = dijkstra(0, graph)[N + 1]
print(K)


import heapq
(xs, ys, xt, yt) = map(int, input().split())
N = int(input())
xyr = []
xyr.append([xs, ys, 0])
for i in range(N):
	(x, y, r) = map(int, input().split())
	xyr.append([x, y, r])
xyr.append([xt, yt, 0])
d = [[float('inf')] * (N + 2) for i in range(N + 2)]
for i in range(N + 2):
	for j in range(N + 2):
		nowd = ((xyr[i][0] - xyr[j][0]) ** 2 + (xyr[i][1] - xyr[j][1]) ** 2) ** 0.5
		nowd = max(0, nowd - xyr[i][2] - xyr[j][2])
		d[i][j] = nowd
		d[j][i] = nowd
ans = [float('inf')] * (N + 2)
ans[0] = 0
used = [False] * (N + 2)
while True:
	v = -1
	for i in range(N + 2):
		if not used[i] and (v == -1 or ans[v] > ans[i]):
			v = i
	if v == -1:
		break
	used[v] = True
	for i in range(N + 2):
		ans[i] = min(ans[i], ans[v] + d[v][i])
print(ans[-1])


from scipy.sparse.csgraph import csgraph_from_dense, dijkstra
(sx, sy, gx, gy) = map(int, input().split())
n = int(input())
arr = [[sx, sy, 0]] + [list(map(int, input().split())) for _ in range(n)] + [[gx, gy, 0]]
g = [[-1] * (n + 2) for _ in range(n + 2)]
for i in range(n + 2):
	(x1, y1, r1) = arr[i]
	for j in range(n + 2):
		(x2, y2, r2) = arr[j]
		g[i][j] = max(0.0, ((x1 - x2) ** 2 + (y1 - y2) ** 2) ** 0.5 - (r1 + r2))
g = csgraph_from_dense(g, null_value=-1)
ans = ((sx - gx) ** 2 + (sy - gy) ** 2) ** 0.5
print(min(ans, dijkstra(g, indices=0)[n + 1]))


from collections import defaultdict
import math

def culcD(a, b):
	(x1, y1, r1) = a
	(x2, y2, r2) = b
	return max(0, math.sqrt((x1 - x2) ** 2 + (y1 - y2) ** 2) - (r1 + r2))
A = []
(xs, ys, xg, yg) = map(int, input().split())
A.append((xs, ys, 0))
A.append((xg, yg, 0))
V = defaultdict(int)
V[0, 1] = culcD(A[0], A[1])
V[1, 0] = culcD(A[0], A[1])
N = int(input())
for i in range(N):
	(x, y, r) = map(int, input().split())
	A.append((x, y, r))
	for j in range(len(A) - 1):
		dist = culcD(A[j], A[-1])
		V[i + 2, j] = dist
		V[j, i + 2] = dist

def dijkstra(n):
	d = [float('inf')] * (n + 2)
	d[0] = 0
	used = [False] * (n + 2)
	while True:
		v = -1
		for i in range(n + 2):
			if used[i] == False and (v == -1 or d[i] < d[v]):
				v = i
		if v == -1:
			break
		used[v] = True
		for j in range(n + 2):
			d[j] = min(d[j], d[v] + V[j, v])
	return d[1]
print(dijkstra(N))


from collections import defaultdict as dd
from heapq import heappop, heappush
import math
(xs, ys, xt, yt) = list(map(int, input().split()))
N = int(input())
Cs = [list(map(int, input().split())) for _ in range(N)]
Cs.append([xs, ys, 0])
Cs.append([xt, yt, 0])
Es = dd(dict)
for i in range(N + 2):
	(xi, yi, ri) = Cs[i]
	for j in range(i + 1, N + 2):
		(xj, yj, rj) = Cs[j]
		Es[i][j] = Es[j][i] = max(0, math.sqrt((xi - xj) ** 2 + (yi - yj) ** 2) - ri - rj)
INF = float('inf')
dists = [INF] * (N + 2)
dists[N] = 0
q = []
close = set()
start = N
heappush(q, (0, start))
while q:
	(d, node) = heappop(q)
	if dists[node] < d:
		continue
	close.add(node)
	for (to, c) in list(Es[node].items()):
		if to in close or dists[to] <= d + c:
			continue
		dists[to] = d + c
		heappush(q, (dists[to], to))
print(dists[N + 1])


import sys
from math import sqrt
input = sys.stdin.readline
from heapq import heappop, heappush
(xs, ys, xt, yt) = map(int, input().split())
N = int(input())
INF = float('inf')
cost = [[INF] * (N + 2) for i in range(N + 2)]
D = [(xs, ys, 0)]
for i in range(N):
	(x, y, r) = map(int, input().split())
	D.append((x, y, r))
D.append((xt, yt, 0))
for i in range(N + 2):
	for j in range(i + 1, N + 2):
		k = max(0, sqrt((D[i][0] - D[j][0]) ** 2 + (D[i][1] - D[j][1]) ** 2) - D[i][2] - D[j][2])
		cost[i][j] = k
		cost[j][i] = k
visit = [0] * (N + 2)
visit[0] = 1
d = [INF] * (N + 2)
d[0] = 0
que = [(0, 0)]
while que:
	(dist, v) = heappop(que)
	if d[v] < dist:
		continue
	if v == N + 1:
		print(d[v])
		exit()
	visit[v] = 1
	for w in range(N + 2):
		if visit[w] == 0 and w != v and (d[w] > d[v] + cost[v][w]):
			d[w] = d[v] + cost[v][w]
			heappush(que, (d[w], w))


import math
import heapq
(x1, y1, x2, y2) = map(int, input().split())
N = int(input())
circles = [(x1, y1, 0), (x2, y2, 0)]
for i in range(N):
	(x, y, r) = map(int, input().split())
	circles.append((x, y, r))
N += 2
INF = 10 ** 12
dists = [[INF] * N for _ in range(N)]
for i in range(N):
	(xi, yi, ri) = circles[i]
	for j in range(N):
		(xj, yj, rj) = circles[j]
		d = math.sqrt(abs(xi - xj) ** 2.0 + abs(yi - yj) ** 2.0) - ri - rj
		dists[i][j] = dists[j][i] = max(d, 0)
mincost = [None] * N
hp = [(0.0, 0)]
while hp:
	(mc, node) = heapq.heappop(hp)
	if mincost[node] is not None:
		continue
	mincost[node] = mc
	for i in range(N):
		if mincost[i] is None:
			heapq.heappush(hp, (mc + dists[node][i], i))
print(mincost[1])


from heapq import *
from math import sqrt

def finddist(a, b):
	(x1, y1, r1) = a
	(x2, y2, r2) = b
	dx = x1 - x2
	dy = y1 - y2
	d = sqrt(dx * dx + dy * dy)
	return max(0, d - r1 - r2)

def dijkstra(c, s, t):
	found = set([(s, 0)])
	dist = {s: 0}
	notfound = set(c[1:])
	edgesinheap = []
	newvert = s
	while notfound:
		if newvert == t:
			return dist[t]
		for x in notfound:
			heappush(edgesinheap, (dist[newvert] + finddist(newvert, x), x, newvert))
		nextvertexfound = False
		while not nextvertexfound:
			(d, nextvert, priv) = heappop(edgesinheap)
			if nextvert not in found:
				nextvertexfound = True
				dist[nextvert] = d
				found.add(nextvert)
				notfound.remove(nextvert)
				newvert = nextvert
	return dist[t]
(xs, ys, xt, yt) = list(map(int, input().split()))
N = int(input())
circles = [(xs, ys, 0), (xt, yt, 0)]
for _ in range(N):
	c = tuple(map(int, input().split()))
	circles.append(c)
edges = []
print(dijkstra(circles, circles[0], circles[1]))


(xs, ys, xe, ye) = map(int, input().split())
n = int(input())
xyr = [tuple(map(int, input().split())) for _ in range(n)]
xyr.append((xs, ys, 0))
xyr.append((xe, ye, 0))
d = [[0] * (n + 2) for _ in range(n + 2)]
for i in range(n + 1):
	for j in range(i + 1, n + 2):
		(x, y, r) = xyr[i]
		(nx, ny, nr) = xyr[j]
		tmp = ((x - nx) ** 2 + (y - ny) ** 2) ** 0.5
		tmp -= r + nr
		tmp = max(tmp, 0)
		d[i][j] = tmp
		d[j][i] = tmp
inf = float('inf')
seen = [inf] * (n + 2)
seen[-2] = 0
mi = set(range(n + 2))
while mi:
	min_idx = 0
	min_d = inf
	for v in mi:
		if min_d > seen[v]:
			min_d = seen[v]
			min_idx = v
	v = min_idx
	mi.discard(v)
	if v == n + 1:
		break
	for nv in mi:
		seen[nv] = min(seen[nv], seen[v] + d[v][nv])
print(seen[-1])


from heapq import heappop, heappush
import sys
input = sys.stdin.readline
from math import sqrt
(xs, ys, xt, yt) = map(int, input().split())
N = int(input())
table = [[10 ** 16] * (N + 2) for i in range(N + 2)]
L = [(xs, ys, 0)]
for i in range(N):
	(x, y, r) = map(int, input().split())
	L.append((x, y, r))
L.append((xt, yt, 0))
for i in range(N + 2):
	for j in range(i + 1, N + 2):
		(x, y, r) = L[i]
		(z, w, l) = L[j]
		k = max(0, sqrt(abs(x - z) ** 2 + abs(y - w) ** 2) - r - l)
		table[i][j] = k
		table[j][i] = k
H = []
H.append((0, 0))
visit = [0] * (N + 2)
visit[0] = 1
val = [10 ** 16] * (N + 2)
val[0] = 0
while H:
	(cost, pt) = heappop(H)
	if val[pt] < cost:
		continue
	if pt == N + 1:
		print(val[pt])
		sys.exit()
	visit[pt] = 1
	for j in range(N + 2):
		if visit[j] == 0 and j != pt and (val[j] > table[j][pt] + val[pt]):
			val[j] = table[j][pt] + val[pt]
			heappush(H, (val[j], j))


from collections import defaultdict, deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random

def LI():
	return [int(x) for x in sys.stdin.readline().split()]

def I():
	return int(sys.stdin.readline())

def LS():
	return [list(x) for x in sys.stdin.readline().split()]

def S():
	res = list(sys.stdin.readline())
	if res[-1] == '\n':
		return res[:-1]
	return res

def IR(n):
	return [I() for i in range(n)]

def LIR(n):
	return [LI() for i in range(n)]

def SR(n):
	return [S() for i in range(n)]

def LSR(n):
	return [LS() for i in range(n)]
sys.setrecursionlimit(1000000)
mod = 1000000007

def A():
	n = I()
	return

def B():
	n = I()
	return

def C():

	def dist(a, b):
		(xa, ya, ra) = a
		(xb, yb, rb) = b
		return max(0, ((xa - xb) ** 2 + (ya - yb) ** 2) ** 0.5 - (ra + rb))
	(xs, ys, xt, yt) = LI()
	n = I()
	p = LIR(n)
	v = [[] for i in range(n + 2)]
	a = (xs, ys, 0)
	b = (xt, yt, 0)
	d = dist(a, b)
	v[0].append((n + 1, d))
	for i in range(n):
		d = dist(a, p[i])
		v[0].append((i + 1, d))
		d = dist(p[i], b)
		v[i + 1].append((n + 1, d))
		for j in range(i + 1, n):
			d = dist(p[i], p[j])
			v[i + 1].append((j + 1, d))
			v[j + 1].append((i + 1, d))
	d = [float('inf')] * (n + 2)
	q = [(0, 0)]
	d[0] = 0
	while q:
		(dx, x) = heappop(q)
		if x > n:
			print(d[x])
			return
		if d[x] < dx:
			continue
		for (y, w) in v[x]:
			nd = dx + w
			if nd < d[y]:
				d[y] = nd
				heappush(q, (nd, y))
	return

def D():
	n = I()
	return

def E():
	n = I()
	return

def F():
	n = I()
	return
C()


import heapq
import math
import os
import sys
if os.getenv('LOCAL'):
	sys.stdin = open('_in.txt', 'r')
sys.setrecursionlimit(2147483647)
INF = float('inf')
IINF = 10 ** 18
MOD = 10 ** 9 + 7
(SX, SY, TX, TY) = list(map(int, sys.stdin.readline().split()))
N = int(sys.stdin.readline())
XYR = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
S = N
T = N + 1
XYR.append([SX, SY, 0])
XYR.append([TX, TY, 0])
graph = [[] for _ in range(N + 2)]
for (i, (xi, yi, ri)) in enumerate(XYR):
	for (j, (xj, yj, rj)) in enumerate(XYR):
		if i == j:
			continue
		d = math.sqrt((xi - xj) ** 2 + (yi - yj) ** 2) - ri - rj
		graph[i].append((max(0, d), j))
heap = [(0, S)]
heapq.heapify(heap)
dist = [IINF] * (N + 2)
while heap:
	(w, v) = heapq.heappop(heap)
	if w > dist[v]:
		continue
	for (dw, u) in graph[v]:
		if w + dw < dist[u]:
			dist[u] = w + dw
			heapq.heappush(heap, (w + dw, u))
print(dist[T])


def flpl():
	return [float(i) for i in input().split()]

def inpl():
	return [int(i) for i in input().split()]
import heapq

def dijkstra(vnum, vs):
	dist = [float('inf') for _ in range(vnum)]
	dist[vs] = 0
	remain = set(range(vnum))
	Q = []
	heapq.heappush(Q, (0, vs))
	while Q:
		(c, vn) = heapq.heappop(Q)
		if vn not in remain:
			continue
		remain.remove(vn)
		for j in remain:
			evnj = edge(vn, j)
			if dist[vn] + evnj < dist[j]:
				dist[j] = dist[vn] + evnj
				heapq.heappush(Q, (dist[j], j))
		if not remain:
			break
	return dist

def edge(s, t):
	return max(((X[s] - X[t]) ** 2 + (Y[s] - Y[t]) ** 2) ** (1 / 2) - (R[s] + R[t]), 0)
(xs, ys, xt, yt) = flpl()
N = int(input())
xyr = [(xs, ys, 0), (xt, yt, 0)] + [inpl() for _ in range(N)]
(X, Y, R) = list(map(list, zip(*xyr)))
D = dijkstra(N + 2, 0)
print(D[1])


import heapq
import sys
input = sys.stdin.buffer.readline

def dijkstra(adj, start):
	dist = [float('inf')] * len(adj)
	dist[start] = 0
	q = []
	heapq.heappush(q, (0, start))
	while q:
		(min_dist, v_from) = heapq.heappop(q)
		if min_dist > dist[v_from]:
			continue
		v_tos = adj[v_from]
		for (v_to, cost) in v_tos:
			if min_dist + cost < dist[v_to]:
				dist[v_to] = min_dist + cost
				heapq.heappush(q, (dist[v_to], v_to))
	return dist

def main():
	(xs, ys, xt, yt) = map(int, input().split())
	N = int(input())
	br = [(xs, ys, 0), (xt, yt, 0)]
	for _ in range(N):
		br.append(tuple(map(int, input().split())))
	adj = [[] for _ in range(N + 3)]
	for i in range(N + 2):
		for j in range(i + 1, N + 2):
			dij = max(((br[i][0] - br[j][0]) ** 2 + (br[i][1] - br[j][1]) ** 2) ** (1 / 2) - (br[i][2] + br[j][2]), 0)
			adj[i + 1].append([j + 1, dij])
			adj[j + 1].append([i + 1, dij])
	print(dijkstra(adj, 1)[2])
main()


from heapq import heappop, heappush, heapify
from collections import deque

class Graph:

	def __init__(self, n, edge, indexed=1):
		self.n = n
		self.edge = edge
		self.indexed = indexed
		self.graph = [[] for _ in range(n)]
		for e in edge:
			self.graph[e[0] - indexed].append((e[1] - indexed, e[2]))
			self.graph[e[1] - indexed].append((e[0] - indexed, e[2]))

	def dijkstra(self, s, INF=10 ** 18, restore_to=None):
		dist = [INF for _ in range(self.n)]
		dist[s] = 0
		heap = [(0, s)]
		prev = [None for _ in range(self.n)]
		while heap:
			(cost, node) = heappop(heap)
			if dist[node] < cost:
				continue
			for (adj, adjcost) in self.graph[node]:
				if dist[node] + adjcost < dist[adj]:
					dist[adj] = dist[node] + adjcost
					prev[adj] = node
					heappush(heap, (dist[adj], adj))
		if restore_to is not None:
			g = restore_to
			if dist[g] == INF:
				return (dist, False)
			path = [g]
			node = g
			while node != s:
				node = prev[node]
				path.append(node)
			return (dist, path[::-1])
		return dist

def dist(p, q):
	(px, py) = p
	(qx, qy) = q
	return ((px - qx) ** 2 + (py - qy) ** 2) ** 0.5
(xs, ys, xt, yt) = map(int, input().split())
s = (xs, ys)
t = (xt, yt)
N = int(input())
barrier = [tuple(map(int, input().split())) for _ in range(N)]
edge = []
edge.append((0, N + 1, dist(s, t)))
for i in range(N):
	(xi, yi, ri) = barrier[i]
	pi = (xi, yi)
	d = max(dist(s, pi) - ri, 0)
	edge.append((0, i + 1, d))
for i in range(N):
	(xi, yi, ri) = barrier[i]
	pi = (xi, yi)
	d = max(dist(t, pi) - ri, 0)
	edge.append((N + 1, i + 1, d))
for i in range(N - 1):
	for j in range(i + 1, N):
		(xi, yi, ri) = barrier[i]
		(xj, yj, rj) = barrier[j]
		pi = (xi, yi)
		pj = (xj, yj)
		d = max(dist(pi, pj) - ri - rj, 0)
		edge.append((i + 1, j + 1, d))
g = Graph(N + 2, edge, 0)
print(g.dijkstra(0)[N + 1])


import math
import heapq
(xs, ys, xt, yt) = map(int, input().split())
N = int(input())
x = [xs] + [0 for i in range(N)] + [xt]
y = [ys] + [0 for i in range(N)] + [yt]
r = [0] + [0 for i in range(N)] + [0]
for i in range(1, N + 1):
	(x[i], y[i], r[i]) = map(int, input().split())
dist = [10 ** 15 for i in range(N + 2)]
dist[0] = 0
adjlist = [[0 for i in range(N + 2)] for j in range(N + 2)]
for i in range(N + 2):
	for j in range(N + 2):
		if i == j:
			continue
		adjlist[i][j] = max(math.sqrt((x[i] - x[j]) ** 2 + (y[i] - y[j]) ** 2) - r[i] - r[j], 0)
q = []
heapq.heappush(q, (0, 0))
while len(q) > 0:
	(d, p) = heapq.heappop(q)
	if dist[p] < d:
		continue
	for j in range(N + 2):
		if p == j:
			continue
		cost = adjlist[p][j]
		if dist[j] > dist[p] + cost:
			dist[j] = dist[p] + cost
			heapq.heappush(q, (dist[j], j))
print(dist[N + 1])


import sys
from collections import deque, defaultdict
import copy
import bisect
sys.setrecursionlimit(10 ** 9)
import math
import heapq
from itertools import product, permutations, combinations
import fractions
from operator import itemgetter
import sys

def input():
	return sys.stdin.readline().strip()
(xs, ys, xt, yt) = list(map(int, input().split()))
N = int(input())
circle = [(xs, ys, 0)]
for i in range(N):
	circle.append(tuple(map(int, input().split())))
circle.append((xt, yt, 0))
graph = [[0] * (N + 2) for _ in range(N + 2)]
for i in range(N + 2):
	for j in range(i):
		dist = ((circle[i][0] - circle[j][0]) ** 2 + (circle[i][1] - circle[j][1]) ** 2) ** 0.5 - circle[i][2] - circle[j][2]
		dist = max(0, dist)
		graph[i][j] = dist
		graph[j][i] = dist
dist = [10 ** 13] * (N + 2)
dist[0] = 0
node_list = []
heapq.heappush(node_list, (0, 0))
while len(node_list) > 0:
	node = heapq.heappop(node_list)
	if dist[node[1]] == node[0]:
		for i in range(N + 2):
			if i != node[1] and dist[i] > node[0] + graph[node[1]][i]:
				dist[i] = node[0] + graph[node[1]][i]
				heapq.heappush(node_list, (dist[i], i))
print(dist[-1])


import math, string, itertools, fractions, heapq, collections, re, array, bisect, sys, random, time
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 10
mod = 10 ** 9 + 7

def main():
	(sx, sy, ex, ey) = list(map(int, input().split()))
	n = int(input())
	f = [False] * n
	a = [list(map(int, input().split())) for _ in range(n)]
	aa = [[inf] * n for _ in range(n)]
	k = [0] * n
	for i in range(n):
		ai = a[i]
		t = math.sqrt((sx - ai[0]) ** 2 + (sy - ai[1]) ** 2) - ai[2]
		if t <= 0:
			t = 0
		k[i] = t
	for i in range(n - 1):
		ai = a[i]
		for j in range(i + 1, n):
			aj = a[j]
			t = math.sqrt((aj[0] - ai[0]) ** 2 + (aj[1] - ai[1]) ** 2) - ai[2] - aj[2]
			if t < 0:
				t = 0
			aa[i][j] = t
			aa[j][i] = t
	while True:
		mi = -1
		mk = inf
		for i in range(n):
			if f[i]:
				continue
			if k[i] < mk:
				mk = k[i]
				mi = i
		if mi < 0:
			break
		aai = aa[mi]
		f[mi] = True
		for j in range(n):
			if aai[j] + k[mi] < k[j]:
				k[j] = aai[j] + k[mi]
	r = math.sqrt((sx - ex) ** 2 + (sy - ey) ** 2)
	for i in range(n):
		ai = a[i]
		t = math.sqrt((ex - ai[0]) ** 2 + (ey - ai[1]) ** 2) - ai[2]
		if t < 0:
			t = 0
		if r > k[i] + t:
			r = k[i] + t
	return r
print(main())


from math import sqrt
import heapq

def calc(arr, i, j):
	d = sqrt((arr[i][0] - arr[j][0]) ** 2 + (arr[i][1] - arr[j][1]) ** 2)
	if arr[i][2] + arr[j][2] <= d:
		return d - arr[i][2] - arr[j][2]
	else:
		return 0

def main():
	(xs, ys, xt, yt) = map(int, input().split())
	n = int(input())
	arr = [list(map(int, input().split())) for _ in range(n)]
	arr.append([xs, ys, 0])
	arr.append([xt, yt, 0])
	n += 2
	st = set()
	for i in range(n):
		st.add(i)
	dist = [float('inf')] * n
	dist[n - 2] = 0
	dist[n - 1] = calc(arr, n - 2, n - 1)
	hq = []
	heapq.heappush(hq, [0, n - 2])
	while len(hq) > 0:
		(_, p) = heapq.heappop(hq)
		if p in st:
			st.remove(p)
			for nxt in st:
				d = calc(arr, p, nxt)
				if dist[nxt] > dist[p] + d:
					dist[nxt] = dist[p] + d
					heapq.heappush(hq, [dist[nxt], nxt])
	print(dist[-1])
main()


import heapq
from math import sqrt

def dijkstra(s, n, g):
	INF = 10 ** 18
	d = [INF] * n
	d[s] = 0
	que = []
	heapq.heappush(que, (0, s))
	while que:
		(dist, v) = heapq.heappop(que)
		if d[v] < dist:
			continue
		for (next_v, cost) in g[v]:
			if d[next_v] > d[v] + cost:
				d[next_v] = d[v] + cost
				heapq.heappush(que, (d[next_v], next_v))
	return d
(xs, ys, xg, yg) = map(int, input().split())
xyrl = []
xyrl.append((xs, ys, 0))
xyrl.append((xg, yg, 0))
n = int(input())
for _ in range(n):
	(x, y, r) = map(int, input().split())
	xyrl.append((x, y, r))
g = [[] for _ in range(n + 2)]
for i in range(n + 2):
	for j in range(n + 2):
		if i == j:
			continue
		(x1, y1, r1) = xyrl[i]
		(x2, y2, r2) = xyrl[j]
		d = sqrt((x2 - x1) ** 2 + (y2 - y1) ** 2) - r1 - r2
		if d < 0:
			d = 0
		g[i].append((j, d))
dists = dijkstra(0, n + 2, g)
print(dists[1])


import numpy as np
from scipy.spatial.distance import cdist
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra
(xs, xy, xt, yt) = map(int, input().split())
N = int(input())
barriers = np.array([(xs, xy, 0), (xt, yt, 0)] + [tuple(map(int, input().split())) for _ in range(N)])
dist = cdist(barriers[:, :2], barriers[:, :2])
dist = np.maximum(dist - barriers[:, 2] - barriers[:, 2][:, None], 0)
length = dist.ravel()
frm = np.repeat(np.arange(N + 2), N + 2)
to = np.tile(np.arange(N + 2), N + 2)
matr = csr_matrix((length, (frm, to)), shape=(N + 2, N + 2))
ans = dijkstra(matr, indices=0)[1]
print(ans)


import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub
from pprint import pprint
sys.setrecursionlimit(10000)

def read_int():
	return int(input())

def read_int_n():
	return list(map(int, input().split()))

def read_float():
	return float(input())

def read_float_n():
	return list(map(float, input().split()))

def read_str():
	return input().strip()

def read_str_n():
	return list(map(str, input().split()))

def error_print(*args):
	print(*args, file=sys.stderr)

def mt(f):
	import time

	def wrap(*args, **kwargs):
		s = time.time()
		ret = f(*args, **kwargs)
		e = time.time()
		error_print(e - s, 'sec')
		return ret
	return wrap

def Dijkstra(g, s):
	d = {}
	q = []
	heapq.heappush(q, (0, s))
	while q:
		(c, u) = heapq.heappop(q)
		if u in d:
			continue
		d[u] = c
		for v in g[u]:
			if v not in d:
				heapq.heappush(q, (g[u][v] + c, v))
	return d

@mt
def slv(N, XY, YS, XT, YT, XYR):
	p = [(XY, YS, 0, -1), (XT, YT, 0, -2)]
	for (i, (x, y, r)) in enumerate(XYR):
		p.append((x, y, r, i))

	def cost(p1, p2):
		c = math.sqrt((p1[0] - p2[0]) ** 2 + (p1[1] - p2[1]) ** 2) - p1[2] - p2[2]
		return max(0, c)
	g = defaultdict(dict)
	for i in range(N + 2):
		for j in range(N + 2):
			if i == j:
				continue
			d = cost(p[i], p[j])
			g[p[i][3]][p[j][3]] = d
			g[p[j][3]][p[i][3]] = d
	return Dijkstra(g, -1)[-2]

def main():
	(XS, YS, XT, YT) = read_int_n()
	N = read_int()
	XYR = [read_int_n() for _ in range(N)]
	print(slv(N, XS, YS, XT, YT, XYR))
main()


(xs, yx, xt, yt) = map(int, input().split())
N = int(input())
l = [[], [xs, yx, 0], [xt, yt, 0]]
for i in range(N):
	l.append(list(map(int, input().split())))
d = [[0] * (N + 3) for _ in range(N + 3)]
for i in range(1, N + 3):
	d[i][i] = 0
for i in range(1, N + 3):
	for j in range(i + 1, N + 3):
		sa = (l[i][0] - l[j][0]) ** 2 + (l[i][1] - l[j][1]) ** 2
		kyori = max(0, sa ** (1 / 2) - l[i][2] - l[j][2])
		d[i][j] = kyori
		d[j][i] = kyori
md = [float('inf')] * (N + 3)
h = [i for i in range(1, N + 3)]
for i in range(1, N + 3):
	md[i] = d[1][i]
seen = [False] * (N + 3)
seen[1] = True
while True:
	v = -1
	for i in h:
		if seen[i] == False and v == -1:
			v = i
		elif seen[i] == False and md[i] < md[v]:
			v = i
	if v == -1:
		break
	seen[v] = True
	for j in range(1, N + 3):
		md[j] = min(md[j], md[v] + d[v][j])
print(md[2])


import sys
input = sys.stdin.readline

def dijkstra(edges, size, src):
	from heapq import heappush, heappop
	INF = 10 ** 18
	dist = [INF] * size
	dist[src] = 0
	pq = [(0, src)]
	while pq:
		(d, v) = heappop(pq)
		if d > dist[v]:
			continue
		for (u, weight) in edges[v]:
			nd = d + weight
			if dist[u] > nd:
				dist[u] = nd
				heappush(pq, (nd, u))
	return dist
(xs, ys, xt, yt) = map(int, input().split())
N = int(input())
xyr = [tuple(map(int, input().split())) for _ in range(N)]
xyr.append((xs, ys, 0))
xyr.append((xt, yt, 0))
edges = [[] for _ in range(N + 2)]
for i in range(N + 1):
	for j in range(i, N + 2):
		(xi, yi, ri) = xyr[i]
		(xj, yj, rj) = xyr[j]
		d = max(0, ((xj - xi) ** 2 + (yj - yi) ** 2) ** 0.5 - (ri + rj))
		edges[i].append((j, d))
		edges[j].append((i, d))
d = dijkstra(edges, N + 2, N)
print(d[N + 1])


from heapq import heappop, heappush
(sx, sy, tx, ty) = list(map(int, input().split()))
n = int(input())
barriers = [tuple(map(int, input().split())) for _ in range(n)]
barriers.append((tx, ty, 0))
barriers.append((sx, sy, 0))
s = n + 1
t = n
q = [(0.0, s)]
visited = [False] * (n + 2)
while q:
	(cost, v) = heappop(q)
	if v == t:
		print(cost)
		break
	if visited[v]:
		continue
	visited[v] = True
	(vx, vy, vr) = barriers[v]
	for u in range(n + 1):
		if visited[u]:
			continue
		(ux, uy, ur) = barriers[u]
		new_cost = max(0, ((vx - ux) ** 2 + (vy - uy) ** 2) ** 0.5 - vr - ur)
		heappush(q, (cost + new_cost, u))


import heapq

def dijkstra(adj: list, start, goal=None):
	num = len(adj)
	dist = [float('inf') for i in range(num)]
	prev = [float('inf') for i in range(num)]
	dist[start] = 0
	q = []
	heapq.heappush(q, (0, start))
	while q:
		(prov_cost, src) = heapq.heappop(q)
		if dist[src] < prov_cost:
			continue
		for dest in range(num):
			cost = adj[src][dest]
			if cost != float('inf') and dist[dest] > dist[src] + cost:
				dist[dest] = dist[src] + cost
				heapq.heappush(q, (dist[dest], dest))
				prev[dest] = src
	return dist
INF = float('inf')
(xs, ys, xt, yt) = map(int, input().split())
n = int(input())
n += 2
li = [None] * n
li[0] = (xs, ys, 0)
li[n - 1] = (xt, yt, 0)
for i in range(n - 2):
	(x, y, r) = map(int, input().split())
	li[i + 1] = (x, y, r)
mat = [[INF] * n for _ in range(n)]
for i in range(n):
	mat[i][i] = 0
	for j in range(i + 1, n):
		(x1, y1, r1) = li[i]
		(x2, y2, r2) = li[j]
		d = ((x1 - x2) ** 2 + (y1 - y2) ** 2) ** 0.5
		res = max(d - r1 - r2, 0)
		mat[i][j] = res
		mat[j][i] = res
d = dijkstra(mat, 0)
print(d[n - 1])


from collections import deque
(sX, sY, eX, eY) = map(int, input().split())
N = int(input())
circles = [(sX, sY, 0)]
for _ in range(N):
	(x, y, r) = map(int, input().split())
	circles.append((x, y, r))
circles.append((eX, eY, 0))
edges = [[float('inf')] * (N + 2) for _ in range(N + 2)]
for (i, (x, y, r)) in enumerate(circles):
	for (j, (u, v, s)) in enumerate(circles):
		d = max(0, ((x - u) ** 2 + (y - v) ** 2) ** 0.5 - (r + s))
		edges[i][j] = d
minDist = [float('inf')] * (N + 2)
confilm = [False] * (N + 2)
minDist[0] = 0
for _ in range(N + 2):
	minNode = (-1, float('inf'))
	for to in range(N + 2):
		if not confilm[to] and minDist[to] < minNode[1]:
			minNode = (to, minDist[to])
	confilm[minNode[0]] = True
	for to in range(N + 2):
		minDist[to] = min(minDist[to], minDist[minNode[0]] + edges[minNode[0]][to])
print(minDist[-1])


from math import sqrt
import numpy as np
from scipy.sparse.csgraph import csgraph_from_dense, shortest_path

def distance(x0, y0, x1, y1):
	return sqrt((x1 - x0) ** 2 + (y1 - y0) ** 2)
(xs, ys, xt, yt, n, *XYR) = map(int, open(0).read().split())
P = [(xs, ys, 0), (xt, yt, 0)] + list(zip(XYR[::3], XYR[1::3], XYR[2::3]))
edges = np.zeros((n + 2, n + 2))
for i in range(n + 1):
	for j in range(i + 1, n + 2):
		dist = distance(P[i][0], P[i][1], P[j][0], P[j][1])
		dist = max(dist - P[i][2] - P[j][2], 0.0)
		edges[i, j] = edges[j, i] = dist
G = csgraph_from_dense(edges, null_value=-1)
print(shortest_path(G, indices=0)[1])


import sys
from heapq import heappush, heappop
input = sys.stdin.readline
(xs, ys, xt, yt) = map(int, input().split())
N = int(input())
x_list = []
y_list = []
r_list = []
x_list.append(xs)
y_list.append(ys)
r_list.append(0)
x_list.append(xt)
y_list.append(yt)
r_list.append(0)
for _ in range(N):
	(x, y, r) = map(int, input().split())
	x_list.append(x)
	y_list.append(y)
	r_list.append(r)
edges = [[] for _ in range(N + 2)]
for i in range(N + 1):
	for j in range(i + 1, N + 2):
		(x1, y1, r1) = (x_list[i], y_list[i], r_list[i])
		(x2, y2, r2) = (x_list[j], y_list[j], r_list[j])
		d = max(0, ((x1 - x2) ** 2 + (y1 - y2) ** 2) ** 0.5 - r1 - r2)
		edges[i].append((j, d))
		edges[j].append((i, d))
INF = 10 ** 10
dist = [INF] * (N + 2)
hq = [(0, 0)]
dist[0] = 0
while hq:
	(cost, node) = heappop(hq)
	if cost > dist[node]:
		continue
	for (next, cost) in edges[node]:
		if dist[node] + cost < dist[next]:
			dist[next] = dist[node] + cost
			heappush(hq, (dist[next], next))
print(dist[1])


def dist(x1, y1, x2, y2):
	return ((x1 - x2) ** 2 + (y1 - y2) ** 2) ** 0.5

def dist_high(index1, index2):
	return max(dist(xyr[index1][0], xyr[index1][1], xyr[index2][0], xyr[index2][1]) - (xyr[index1][2] + xyr[index2][2]), 0)

def min_value_index(array):
	min_value = float('inf')
	min_index = -1
	for (i, v) in array:
		if min_value > v:
			min_value = v
			min_index = i
	return (min_value, min_index)
(stx, sty, enx, eny) = map(int, input().split())
n = int(input())
xyr = [[stx, sty, 0]] + [list(map(int, input().split())) for x in range(n)] + [[enx, eny, 0]]
nodes = {x: float('inf') for x in range(len(xyr))}
nodes[0] = 0
now = 0
while now != len(xyr) - 1:
	for i in nodes.keys():
		if i == now:
			continue
		nodes[i] = min(nodes[i], nodes[now] + dist_high(now, i))
	del nodes[now]
	now = min_value_index(nodes.items())[1]
print(nodes[n + 1])


import math, heapq, sys
input = sys.stdin.readline
(xs, ys, xe, ye) = map(int, input().split())
cs = [(xs, ys, 0), (xe, ye, 0)]
N = int(input())
for i in range(N):
	cs.append(tuple(map(int, input().split())))

def calc_cost(i, j):
	if i == j:
		return float('inf')
	(x1, y1, r1) = cs[i]
	(x2, y2, r2) = cs[j]
	cost = max(0, math.hypot(x1 - x2, y1 - y2) - r1 - r2)
	return cost
INF = float('inf')
direct = calc_cost(0, 1)
hq = []
for i in range(1, N + 2):
	c = calc_cost(0, i)
	if c > direct:
		continue
	hq.append((c, i))
heapq.heapify(hq)
not_visited = set(range(1, N + 2))
cost = [0] + [INF] * (N + 1)
while hq:
	(c, v) = heapq.heappop(hq)
	if v not in not_visited:
		continue
	if v == 1:
		print(c)
		exit()
	cost[v] = c
	not_visited.remove(v)
	for to in not_visited:
		newcost = calc_cost(v, to)
		if cost[to] <= cost[v] + newcost:
			continue
		if direct < cost[v] + newcost:
			continue
		heapq.heappush(hq, (cost[v] + newcost, to))


import bisect, copy, heapq, math, sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product

def input():
	return sys.stdin.readline()[:-1]

def ruiseki(lst):
	return [0] + list(accumulate(lst))

def celi(a, b):
	return -(-a // b)
sys.setrecursionlimit(5000000)
mod = pow(10, 9) + 7
al = [chr(ord('a') + i) for i in range(26)]
direction = [[1, 0], [0, 1], [-1, 0], [0, -1]]
xy = list(map(int, input().split()))
n = int(input())
xyr = [list(map(int, input().split())) for i in range(n)]

def dijkstra(s, e):
	hq = [(0, s)]
	heapq.heapify(hq)
	cost = [float('inf')] * n
	cost[s] = 0
	while hq:
		(c, v) = heapq.heappop(hq)
		if c > cost[v]:
			continue
		for (d, u) in e[v]:
			tmp = d + cost[v]
			if tmp < cost[u]:
				cost[u] = tmp
				heapq.heappush(hq, (tmp, u))
	return cost
(n, w) = (n, (n + 2) * (n + 1) // 2)
edge = [[] for i in range(n + 2)]
for i in range(n):
	for j in range(i + 1, n):
		(x1, y1, r1) = xyr[i]
		(x2, y2, r2) = xyr[j]
		dis = math.sqrt((x2 - x1) ** 2 + (y2 - y1) ** 2)
		edge[i + 1].append((max(0, dis - r1 - r2), j + 1))
		edge[j + 1].append((max(0, dis - r1 - r2), i + 1))
for i in range(n):
	(x1, y1, r1) = xyr[i]
	dis = math.sqrt((xy[0] - x1) ** 2 + (xy[1] - y1) ** 2)
	edge[0].append((max(0, dis - r1), i + 1))
	edge[i + 1].append((max(0, dis - r1), 0))
	dis = math.sqrt((xy[2] - x1) ** 2 + (xy[3] - y1) ** 2)
	edge[n + 1].append((max(0, dis - r1), i + 1))
	edge[i + 1].append((max(0, dis - r1), n + 1))
edge[0].append((math.sqrt((xy[0] - xy[2]) ** 2 + (xy[1] - xy[3]) ** 2), n + 1))
edge[n + 1].append((math.sqrt((xy[0] - xy[2]) ** 2 + (xy[1] - xy[3]) ** 2), 0))
n = n + 2
print(dijkstra(0, edge)[-1])


(a, b, c, d) = map(int, input().split())
N = int(input())

def dijkstra(s, n, w, cost):
	d = [float('inf')] * n
	used = [False] * n
	d[s] = 0
	while True:
		v = -1
		for i in range(n):
			if not used[i] and v == -1:
				v = i
			elif not used[i] and d[i] < d[v]:
				v = i
		if v == -1:
			break
		used[v] = True
		for j in range(n):
			d[j] = min(d[j], d[v] + cost[v][j])
	return d
R = [0] * (N + 2)
A = []
for i in range(N):
	(x, y, r) = map(int, input().split())
	A.append((x, y))
	R[i] = r
A.append((a, b))
A.append((c, d))
cost = [[float('inf') for i in range(N + 2)] for i in range(N + 2)]
for i in range(N + 1):
	for j in range(i + 1, N + 2):
		d = (A[i][0] - A[j][0]) ** 2 + (A[i][1] - A[j][1]) ** 2
		cost[i][j] = max(0, d ** 0.5 - (R[i] + R[j]))
		cost[j][i] = max(0, d ** 0.5 - (R[i] + R[j]))
D = dijkstra(N, N + 2, (N + 2) * (N + 1) // 2, cost)
print(D[N + 1])


import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10 ** 9))
write = lambda x: sys.stdout.write(x + '\n')
(xs, ys, xt, yt) = list(map(int, input().split()))
n = int(input())
xyr = [None] * (n + 2)
for i in range(n):
	xyr[i] = tuple(map(int, input().split()))
from itertools import product
ns = [[] for _ in range(n + 2)]
s = n
t = n + 1
xyr[s] = (xs, ys, 0)
xyr[t] = (xt, yt, 0)
for (i, j) in product(list(range(n + 2)), list(range(n + 2))):
	if i < j:
		d = max(0, ((xyr[i][0] - xyr[j][0]) ** 2 + (xyr[i][1] - xyr[j][1]) ** 2) ** 0.5 - (xyr[i][2] + xyr[j][2]))
		ns[i].append((d, j))
		ns[j].append((d, i))

def dijkstra(start):
	import heapq
	vals = [None] * (n + 2)
	h = [(0, start)]
	vals[start] = 0
	while h:
		(val, u) = heapq.heappop(h)
		if u == t:
			break
		if val > vals[u]:
			continue
		for (d, v) in ns[u]:
			if vals[v] is None or vals[v] > val + d:
				vals[v] = val + d
				heapq.heappush(h, (vals[v], v))
	return vals
vals = dijkstra(s)
ans = vals[t]
print(ans)


from heapq import *

def dijkstra(graph, initial):
	visited = {initial: 0}
	(h, path) = ([(0, initial)], {})
	nodes = set(graph.keys())
	while nodes and h:
		(current_weight, min_node) = heappop(h)
		while h and min_node not in nodes:
			(current_weight, min_node) = heappop(h)
		if not h and min_node not in nodes:
			break
		nodes.remove(min_node)
		for (v, w) in graph[min_node]:
			weight = w + current_weight
			if v not in visited or weight < visited[v]:
				visited[v] = weight
				heappush(h, (weight, v))
				path[v] = min_node
	return (visited, path)
(xstart, ystart, xtarget, ytarget) = map(int, input().split())
N = int(input())
circs = [tuple(map(int, input().split())) for _ in range(N)]
graph = {i: [] for i in range(N + 2)}
from math import sqrt
for i in range(N):
	(xi, yi, ri) = circs[i]
	for j in range(i):
		(xj, yj, rj) = circs[j]
		d = max(sqrt((xi - xj) ** 2 + (yi - yj) ** 2) - ri - rj, 0)
		graph[i].append((j, d))
		graph[j].append((i, d))
	dst = max(sqrt((xi - xstart) ** 2 + (yi - ystart) ** 2) - ri, 0)
	graph[i].append((N, dst))
	graph[N].append((i, dst))
	dtgt = max(sqrt((xi - xtarget) ** 2 + (yi - ytarget) ** 2) - ri, 0)
	graph[i].append((N + 1, dtgt))
	graph[N + 1].append((i, dtgt))
dsrctgt = sqrt((xstart - xtarget) ** 2 + (ystart - ytarget) ** 2)
graph[N].append((N + 1, dsrctgt))
graph[N + 1].append((N, dsrctgt))
(visited, _) = dijkstra(graph, N)
print(visited[N + 1])


from math import sqrt
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix
(xs, ys, xt, yt) = list(map(int, input().split()))
n = int(input())
xyr = [list(map(int, input().split())) for _ in range(n)]
xyr.append([xs, ys, 0])
xyr.append([xt, yt, 0])
row = []
col = []
cost = []
for (i, (xi, yi, ri)) in enumerate(xyr):
	for (j, (xj, yj, rj)) in enumerate(xyr[i + 1:], i + 1):
		row.append(i)
		col.append(j)
		dist = max(0, sqrt((xi - xj) ** 2 + (yi - yj) ** 2) - ri - rj)
		cost.append(dist)
g = csr_matrix((cost, (row, col)), shape=(n + 2, n + 2))
d = dijkstra(g, directed=False, indices=n)
ans = d[n + 1]
print(ans)


from heapq import heappush, heappop
from math import sqrt
inf = float('inf')
(xs, ys, xt, yt) = map(int, input().split())
n = int(input())
q = []
l = [(xs, ys, 0), (xt, yt, 0)] + [tuple(map(int, input().split())) for _ in range(n)]
sizeV = len(l)
rests = set(range(sizeV))
cost = [inf] * sizeV
cost[0] = 0
heappush(q, (0, 0))
while q:
	(c1, i) = heappop(q)
	if c1 > cost[i]:
		continue
	rests.remove(i)
	if not rests:
		break
	(xi, yi, ri) = l[i]
	for j in rests:
		(xj, yj, rj) = l[j]
		d = max(0.0, sqrt((xj - xi) ** 2 + (yj - yi) ** 2) - ri - rj)
		c2 = c1 + d
		if c2 < cost[j]:
			cost[j] = c2
			heappush(q, (c2, j))
print(cost[1])


import sys
stdin = sys.stdin
sys.setrecursionlimit(10 ** 5)

def li():
	return map(int, stdin.readline().split())

def li_():
	return map(lambda x: int(x) - 1, stdin.readline().split())

def lf():
	return map(float, stdin.readline().split())

def ls():
	return stdin.readline().split()

def ns():
	return stdin.readline().rstrip()

def lc():
	return list(ns())

def ni():
	return int(stdin.readline())

def nf():
	return float(stdin.readline())
from math import sqrt
from heapq import heappush, heappop

class Node(object):

	def __init__(self, num, x, y, r):
		self.num = num
		self.x = x
		self.y = y
		self.r = r

class Graph(object):

	def __init__(self, num):
		self.graph = [[] for _ in range(num)]
		self.nodes = []

	def calc_edge_len(self, node1, node2):
		dist = sqrt((node1.x - node2.x) ** 2 + (node1.y - node2.y) ** 2) - node1.r - node2.r
		if dist <= 0:
			return 0
		else:
			return dist

	def add_edge(self, node1, node2):
		edge_len = self.calc_edge_len(node1, node2)
		self.graph[node1.num].append((edge_len, node2.num))
		self.graph[node2.num].append((edge_len, node1.num))

	def get_graph(self):
		return self.graph

def dijkstra(graph: list, node: int, start: int, goal: int) -> int:
	INF = float('inf')
	dist = [INF] * node
	dist[start] = 0
	heap = [(0, start)]
	visited = [False] * node
	while heap:
		(cost, cur_node) = heappop(heap)
		if visited[cur_node]:
			continue
		visited[cur_node] = True
		if cur_node == goal:
			return dist[goal]
		for (nex_cost, nex_node) in graph[cur_node]:
			dist_cand = dist[cur_node] + nex_cost
			if dist_cand < dist[nex_node]:
				dist[nex_node] = dist_cand
				heappush(heap, (dist[nex_node], nex_node))
	return dist[goal]
(xs, ys, xt, yt) = li()
n = ni()
g = Graph(n + 2)
g.nodes.append(Node(0, xs, ys, 0))
g.nodes.append(Node(1, xt, yt, 0))
for i in range(n):
	(x, y, r) = li()
	g.nodes.append(Node(i + 2, x, y, r))
for i in range(len(g.nodes)):
	for j in range(i + 1, len(g.nodes)):
		g.add_edge(g.nodes[i], g.nodes[j])
graph = g.get_graph()
dist = dijkstra(graph, n + 2, 0, 1)
print(dist)


from heapq import heappush, heappop, heapify
INF = 10 ** 30

def dijkstra(G, s, n):
	que = [(0, s)]
	dist = [INF] * n
	dist[s] = 0
	while que:
		(mincost, u) = heappop(que)
		if mincost > dist[u]:
			continue
		for (c, v) in G[u]:
			if dist[u] + c < dist[v]:
				dist[v] = dist[u] + c
				heappush(que, (dist[v], v))
	return dist
(sx, sy, gx, gy) = map(int, input().split())
N = int(input())
(X, Y, R) = ([sx, gx], [sy, gy], [0, 0])
for i in range(N):
	(t, m, p) = map(int, input().split())
	X.append(t)
	Y.append(m)
	R.append(p)
G = [[] for i in range(N + 2)]
for i in range(N + 2):
	for j in range(i):
		d = max(0, ((X[i] - X[j]) ** 2 + (Y[i] - Y[j]) ** 2) ** 0.5 - R[i] - R[j])
		G[i].append((d, j))
		G[j].append((d, i))
dist = dijkstra(G, 0, N + 2)
print(dist[1])


import sys
read = sys.stdin.read
readline = sys.stdin.readline
(xs, ys, xt, yt) = map(int, readline().split())
(n,) = map(int, readline().split())
xyr = [tuple(map(int, readline().split())) for _ in range(n)] + [(xs, ys, 0), (xt, yt, 0)]

def Dijkstra_matrix(d, start):
	n = len(d)
	INF = float('inf')
	dist = d[start][:]
	used = [0] * n
	used[start] = 1
	for _ in range(n - 1):
		d0 = INF
		idx = -1
		for i in range(n):
			if not used[i] and dist[i] < d0:
				idx = i
				d0 = dist[i]
		if idx == -1:
			return dist
		else:
			used[idx] = 1
			for j in range(n):
				if not used[j] and dist[j] > dist[idx] + d[idx][j]:
					dist[j] = dist[idx] + d[idx][j]
	return dist
from math import hypot
d = [[max(0.0, hypot(xi - xj, yi - yj) - ri - rj) for (xj, yj, rj) in xyr] for (xi, yi, ri) in xyr]
dist = Dijkstra_matrix(d, n)
print(dist[-1])


import sys
input = sys.stdin.readline

def I():
	return int(input())

def MI():
	return map(int, input().split())

def LI():
	return list(map(int, input().split()))

def main():
	import heapq

	class Dijkstra:

		class Edge:

			def __init__(self, _to, _cost):
				self.to = _to
				self.cost = _cost

		def __init__(self, V, inf):
			self.inf = inf
			self.G = [[] for _ in range(V)]
			self._E = 0
			self._V = V

		def E(self):
			return self._E

		def V(self):
			return self._V

		def add(self, _from, _to, _cost):
			self.G[_from].append(self.Edge(_to, _cost))
			self._E += 1

		def add2(self, _from, _to, _cost):
			self.G[_from].append(self.Edge(_to, _cost))
			self.G[_to].append(self.Edge(_from, _cost))
			self._E += 2

		def shortest_path(self, s):
			que = []
			d = [self.inf] * self.V()
			d[s] = 0
			heapq.heappush(que, (0, s))
			while len(que) != 0:
				(cost, v) = heapq.heappop(que)
				if d[v] < cost:
					continue
				for i in range(len(self.G[v])):
					e = self.G[v][i]
					if d[e.to] > d[v] + e.cost:
						d[e.to] = d[v] + e.cost
						heapq.heappush(que, (d[e.to], e.to))
			return d
	mod = 10 ** 9 + 7
	L = LI()
	N = I()
	X = [0] * (N + 2)
	Y = [0] * (N + 2)
	R = [0] * (N + 2)
	X[0] = L[0]
	X[-1] = L[2]
	Y[0] = L[1]
	Y[-1] = L[3]
	for i in range(N):
		(X[i + 1], Y[i + 1], R[i + 1]) = MI()
	djk = Dijkstra(N + 2, 10 ** 20)
	for i in range(N + 2):
		for j in range(i + 1, N + 2):
			diff = ((X[i] - X[j]) ** 2 + (Y[i] - Y[j]) ** 2) ** 0.5
			cost = max(diff - R[i] - R[j], 0)
			djk.add2(i, j, cost)
	D = djk.shortest_path(0)
	print(D[-1])
main()


import sys
input = sys.stdin.readline

def dijkstra(edge_adj: list, node: int, start: int) -> list:
	inf = 3 * 10 ** 9
	dist = [inf] * node
	used = [False] * node
	dist[start] = 0
	while True:
		v = -1
		for i in range(node):
			if not used[i] and (v == -1 or dist[v] > dist[i]):
				v = i
		if v == -1:
			break
		used[v] = True
		for i in range(node):
			if dist[i] > dist[v] + edge_adj[v][i]:
				dist[i] = dist[v] + edge_adj[v][i]
	return dist
(xs, ys, xt, yt) = map(int, input().split())
n = int(input())
circles = [(xs, ys, 0), (xt, yt, 0)]
for i in range(n):
	circles.append(tuple(map(int, input().split())))
n += 2
edges = [[0] * n for i in range(n)]
for i in range(n):
	for j in range(i + 1, n):
		dist = ((circles[i][0] - circles[j][0]) ** 2 + (circles[i][1] - circles[j][1]) ** 2) ** 0.5
		cost = max(0, dist - circles[i][2] - circles[j][2])
		edges[i][j] = cost
		edges[j][i] = cost
dist = dijkstra(edges, n, 0)
print(dist[1])


import sys
input = sys.stdin.readline
from collections import defaultdict, deque
from itertools import combinations
from heapq import heappush, heappop
(xs, ys, xt, yt) = map(int, input().split())
N = int(input())
xyr = [list(map(int, input().split())) for i in range(N)]
xyr = [[xs, ys, 0]] + xyr + [[xt, yt, 0]]
cost = {}
for s in range(0, N + 1):
	for t in range(s + 1, N + 2):
		(x1, y1, r1) = xyr[s]
		(x2, y2, r2) = xyr[t]
		R = pow((x2 - x1) ** 2 + (y2 - y1) ** 2, 0.5)
		c = max(0, R - r1 - r2)
		cost[s, t] = c
		cost[t, s] = c
h = [(0, 0)]
dist = [10 ** 15] * (N + 2)
dist[0] = 0
while h:
	(d, v) = heappop(h)
	if dist[v] < d:
		continue
	for nv in range(N + 2):
		if v == nv:
			continue
		temp = d + cost[v, nv]
		if temp < dist[nv]:
			dist[nv] = temp
			heappush(h, (temp, nv))
print(dist[N + 1])


(a, b, c, d) = map(int, input().split())
n = int(input())
s = [[a, b, 0]] + [list(map(int, input().split())) for i in range(n)] + [[c, d, 0]]
c = [[0] * (n + 2) for i in range(n + 2)]
for i in range(n + 2):
	for j in range(i, n + 2):
		c[i][j] = c[j][i] = max(0, ((s[i][0] - s[j][0]) ** 2 + (s[i][1] - s[j][1]) ** 2) ** 0.5 - s[i][2] - s[j][2])
c = tuple(c)
n += 2
a = [float('INF')] * n
b = [1] * n
a[0] = 0
while 1:
	v = -1
	for i in range(n):
		if v == -1 and b[i]:
			v = i
		elif b[i] and a[i] < a[v]:
			v = i
	if v == -1:
		break
	b[v] = 0
	for j in range(n):
		a[j] = min(a[j], a[v] + c[v][j])
print(a[-1])


from heapq import heapify, heappop, heappush
import sys
import math
input = sys.stdin.readline
(xs, ys, xt, yt) = list(map(int, input().split()))
N = int(input())
A = [(xs, ys, 0)]
for i in range(N):
	A.append(tuple(map(int, input().split())))
A.append((xt, yt, 0))
task = [[0.0, 0]]
heapify(task)
visited = set()
while task:
	while task:
		(c, p) = heappop(task)
		if p not in visited:
			break
		if not task:
			print('error')
			return
	if p == N + 1:
		print(c)
		return
	visited.add(p)
	(xp, yp, rp) = A[p]
	for q in range(N + 2):
		if q not in visited:
			(xq, yq, rq) = A[q]
			l = max(0.0, math.sqrt((xq - xp) ** 2 + (yq - yp) ** 2) - rq - rp)
			heappush(task, [c + l, q])


import heapq

def dijkstra_heap(N, s, edge):
	d = [float('inf')] * N
	used = [False] * N
	d[s] = 0
	used[s] = True
	edgelist = []
	for (v, w) in enumerate(edge[s]):
		heapq.heappush(edgelist, (w, v))
	while len(edgelist):
		minedge = heapq.heappop(edgelist)
		v = minedge[1]
		if used[v]:
			continue
		d[v] = minedge[0]
		used[v] = True
		for (u, w) in enumerate(edge[v]):
			if not used[u]:
				heapq.heappush(edgelist, (d[v] + w, u))
	return d
(A, B, C, D) = map(int, input().split())
N = int(input())
d = [[0] * (N + 2) for _ in range(N + 2)]
X = [0] * N
Y = [0] * N
R = [0] * N
for i in range(N):
	(X[i], Y[i], R[i]) = map(int, input().split())
d[0][-1] = ((C - A) ** 2 + (D - B) ** 2) ** 0.5
d[-1][0] = ((C - A) ** 2 + (D - B) ** 2) ** 0.5
for i in range(1, N + 1):
	d_s = max(0, ((X[i - 1] - A) ** 2 + (Y[i - 1] - B) ** 2) ** 0.5 - R[i - 1])
	d_e = max(0, ((X[i - 1] - C) ** 2 + (Y[i - 1] - D) ** 2) ** 0.5 - R[i - 1])
	(d[0][i], d[i][0]) = (d_s, d_s)
	(d[N + 1][i], d[i][N + 1]) = (d_e, d_e)
	for j in range(1, N + 1):
		d[i][j] = max(((X[i - 1] - X[j - 1]) ** 2 + (Y[i - 1] - Y[j - 1]) ** 2) ** 0.5 - R[i - 1] - R[j - 1], 0)
s = 0
d = dijkstra_heap(N + 2, s, d)
print(d[-1])


(sX, sY, eX, eY) = map(int, input().split())
N = int(input())
circles = [(sX, sY, 0)]
for _ in range(N):
	(cx, cy, r) = map(int, input().split())
	circles.append((cx, cy, r))
circles.append((eX, eY, 0))
edges = [[float('inf')] * (N + 2) for _ in range(N + 2)]
for (i, (cx1, cy1, r1)) in enumerate(circles):
	for (j, (cx2, cy2, r2)) in enumerate(circles):
		cDist = ((cx1 - cx2) ** 2 + (cy1 - cy2) ** 2) ** 0.5
		dist = max(0, cDist - r1 - r2)
		edges[i][j] = dist
		edges[j][i] = dist
minDist = [float('inf')] * (N + 2)
minDist[0] = 0
confilm = [False] * (N + 2)
for _ in range(N + 2):
	md = float('inf')
	minNode = -1
	for n in range(N + 2):
		if not confilm[n] and md > minDist[n]:
			minNode = n
			md = minDist[n]
	confilm[minNode] = True
	for to in range(N + 2):
		minDist[to] = min(minDist[to], minDist[minNode] + edges[minNode][to])
print(minDist[-1])


from struct import pack, unpack
import math
from heapq import heapify, heappush as hpush, heappop as hpop

class FibonacciHeap:

	def __init__(self, mm):
		self.inf = 1 << 100
		self.mm = mm
		self.roots = [[] for _ in range(mm)]
		self.min = self.inf
		self.minroot = None

	def add(self, v):
		nd = self.node(v)
		self.add_node(nd)
		return nd

	def add_node(self, nd):
		k = nd.order
		if nd.value < self.min:
			self.min = nd.value
			self.minroot = nd
		self.roots[k].append(nd)

	def setmin(self):
		mi = self.inf
		mirt = None
		for (i, rt) in enumerate(self.roots):
			while len(rt) >= 2:
				nd1 = rt.pop()
				nd2 = rt.pop()
				self.roots[i + 1].append(nd1.meld(nd2))
			if len(rt) and rt[0].value < mi:
				mi = rt[0].value
				mirt = rt[0]
		self.min = mi
		self.minroot = mirt
		return self.minroot

	def pop(self):
		nd = self.minroot
		mi = nd.value
		self.roots[nd.order].remove(nd)
		ch = nd.repChild
		if ch:
			nd = ch.right
			while 1:
				nnd = nd.right
				self.add_node(nd)
				l = nd.left
				r = nd.right
				if r != nd:
					nd.right = nd
					nd.left = nd
					l.right = r
					r.left = l
				nd.parent = None
				if nd == ch:
					break
				nd = nnd
		self.setmin()
		return mi

	class node:

		def __init__(self, value):
			self.parent = None
			self.left = self
			self.right = self
			self.repChild = None
			self.order = 0
			self.marked = 0
			self.value = value

		def meld(self, other):
			if self.value > other.value:
				return other.meld(self)
			other.parent = self
			if not self.repChild:
				self.repChild = other
			else:
				l = self.repChild
				r = l.right
				l.right = other
				r.left = other
				other.left = l
				other.right = r
			self.order += 1
			return self

	def movetop(self, nd):
		p = nd.parent
		nd.marked = 0
		if not p:
			return nd
		l = nd.left
		r = nd.right
		if r != nd:
			p.repChild = r
			nd.right = nd
			nd.left = nd
			l.right = r
			r.left = l
		else:
			p.repChild = None
		nd.parent = None
		self.add_node(nd)
		if not p.parent:
			self.roots[p.order].remove(p)
			p.order -= 1
			self.add_node(p)

	def prioritize(self, nd, v):
		p = nd.parent
		nd.value = v
		if v < self.min:
			self.min = v
			self.minroot = nd
		if not p or p.value <= v:
			return nd
		self.movetop(nd)
		nn = p
		while nn.parent:
			if nn.marked == 0:
				nn.marked = 1
				break
			else:
				p = nn.parent
				self.movetop(nn)
				nn = p
		return nd

	def debug(self):

		def _debug(nd):
			if not nd:
				return ''
			s = str(nd.value) + ('(' + str(nd.left.value) + '-' + str(nd.right.value) + ')' if nd != nd.right else '')
			if nd.repChild:
				s += '[C=' + str(nd.repChild.value) + ']'
			if nd.parent:
				s += '[P=' + str(nd.parent.value) + ']'
			if not nd.repChild:
				return s
			ss = []
			ch = nd.repChild
			idch = id(ch)
			nd = ch.right
			while 1:
				ss.append(_debug(nd))
				if id(nd) == idch:
					break
				nd = nd.right
			s += '[' + ', '.join(map(str, ss)) + ']'
			return s
		RE = []
		for (i, root) in enumerate(self.roots):
			for nd in root:
				if nd:
					RE.append('<' + str(i) + '>' + _debug(nd))
		s = 'min=' + str(self.min) + ' '
		print(s + ' - '.join(map(str, RE)))
(xs, ys, xt, yt) = list(map(int, input().split()))
N = int(input())
X = [(xs, ys, 0), (xt, yt, 0)]
for _ in range(N):
	(x, y, r) = list(map(int, input().split()))
	X.append((x, y, r))
N += 2
DD = [[0] * N for _ in range(N)]
for i in range(N):
	(xi, yi, ri) = X[i]
	for j in range(N):
		(xj, yj, rj) = X[j]
		DD[i][j] = max(math.sqrt((xi - xj) ** 2 + (yi - yj) ** 2) - (ri + rj), 0)
m = 1023

def dijkstra(n, E, i0=0):
	fb = FibonacciHeap(100)
	inf = unpack('q', pack('d', 10 ** 10 / 1))[0]
	D = [10 ** 10 / 1] * n
	done = [0] * n
	D[i0] = 0
	V = []
	for i in range(n):
		v = (unpack('q', pack('d', 0.0 if i == i0 else 10 ** 10 / 1))[0] | m) - (m - i)
		V.append(fb.add(v))
	while fb.minroot:
		di = fb.pop()
		(d, i) = (unpack('d', pack('q', (di | m) - m))[0], di & m)
		done[i] = 1
		for (j, w) in enumerate(DD[i]):
			if done[j] or j == i:
				continue
			nd = d + w
			if D[j] > nd:
				v = (unpack('q', pack('d', nd))[0] | m) - (m - j)
				fb.prioritize(V[j], v)
				D[j] = nd
	return D
print(dijkstra(N, X)[1])


(xs, ys, xt, yt) = list(map(int, input().split()))
n = int(input())
v = [(xs, ys, 0), (xt, yt, 0)]
for i in range(n):
	(x, y, r) = list(map(int, input().split()))
	v.append((x, y, r))
path = [[] for i in range(n + 2)]
for i in range(n + 1):
	for j in range(i + 1, n + 2):
		l = max(0, ((v[i][0] - v[j][0]) ** 2 + (v[i][1] - v[j][1]) ** 2) ** 0.5 - v[i][2] - v[j][2])
		path[i].append((j, l))
		path[j].append((i, l))
import heapq

def Dijkstra(edge, start, v):
	d = [float('inf')] * v
	d[start] = 0
	pq = [(0, start)]
	heapq.heapify(pq)
	while pq:
		(dist, p) = heapq.heappop(pq)
		if dist > d[p]:
			continue
		for (to, cost) in edge[p]:
			if d[to] <= dist + cost:
				continue
			d[to] = dist + cost
			heapq.heappush(pq, (d[to], to))
	return d
d = Dijkstra(path, 0, n + 2)
print(d[1])


from heapq import heappush, heappop

def read():
	return int(input())

def reads():
	return [int(x) for x in input().split()]
q = reads()
s = q[0] + q[1] * 1j
t = q[2] + q[3] * 1j
N = read()
p = []
r = []
for i in range(N):
	q = reads()
	p.append(q[0] + q[1] * 1j)
	r.append(q[2])
E = [[0] * (N + 2) for _ in range(N + 2)]
for i in range(N):
	for j in range(N):
		E[i][j] = max(abs(p[i] - p[j]) - r[i] - r[j], 0)
for i in range(N):
	E[N][i] = E[i][N] = max(abs(p[i] - s) - r[i], 0)
	E[N + 1][i] = E[i][N + 1] = max(abs(p[i] - t) - r[i], 0)
E[N][N + 1] = E[N + 1][N] = abs(t - s)
INF = 10 ** 15 * 1.0
dist = [E[N][i] for i in range(N + 2)] + [INF]
stab = [False] * (N + 2)
stab[N] = True
for _ in range(N + 1):
	i = N + 2
	for j in range(N + 2):
		if not stab[j] and dist[j] < dist[i]:
			i = j
	stab[i] = True
	for j in range(N + 2):
		dist[j] = min(dist[j], dist[i] + E[i][j])
print(dist[N + 1])


import heapq

def dijkstra(s):
	inf = pow(10, 10)
	dist = [inf] * (n + 2)
	dist[s] = 0
	c = [0] * (n + 2)
	p = []
	heapq.heapify(p)
	heapq.heappush(p, (dist[s], s))
	while p:
		(d, u) = heapq.heappop(p)
		if dist[u] < d:
			continue
		c[u] = 1
		for g in G[u]:
			if c[g[0]] == 0 and dist[u] + g[1] < dist[g[0]]:
				dist[g[0]] = dist[u] + g[1]
				heapq.heappush(p, (dist[g[0]], g[0]))
	return dist[n + 1]
(xs, ys, xt, yt) = map(int, input().split())
n = int(input())
s = [list(map(int, input().split())) for _ in range(n)]
s.insert(0, [xs, ys, 0])
s.append([xt, yt, 0])
G = [[] for _ in range(n + 2)]
for i in range(n + 2):
	for j in range(n + 2):
		if not i == j:
			G[i].append([j, max(0, (pow(s[i][0] - s[j][0], 2) + pow(s[i][1] - s[j][1], 2)) ** (1 / 2) - s[i][2] - s[j][2])])
ans = dijkstra(0)
print(ans)


from math import dist
from scipy.sparse.csgraph import dijkstra, csgraph_from_dense
from numpy import full, inf
from itertools import combinations
(sx, sy, tx, ty, N, *XYR) = map(int, open(0).read().split())
A = [(sx, sy, 0), (tx, ty, 0)] + list(zip(*[iter(XYR)] * 3))
D = full((N + 2, N + 2), inf)
for ((i, (ax, ay, ad)), (j, (bx, by, bd))) in combinations(enumerate(A), 2):
	D[i][j] = max(0, dist((ax, ay), (bx, by)) - ad - bd)
print(dijkstra(csgraph_from_dense(D, null_value=inf), False, 0)[1])


import sys
import math
import heapq
input = sys.stdin.readline

class Vec:

	def __init__(self, x, y):
		self.x = x
		self.y = y

	def move(self, x, y):
		return Vec(self.x + x, self.y + y)

	def rotate(self, theta):
		x = self.x * math.cos(theta) - self.y * math.sin(theta)
		y = self.x * math.sin(theta) + self.y * math.cos(theta)
		return Vec(x, y)

	def theta(self):
		if self.x == 0:
			if self.y > 0:
				return math.pi / 2
			elif self.y < 0:
				return 3 * math.pi / 2
			else:
				return 0
		ret = math.atan(self.y / self.x)
		if self.x < 0:
			ret += math.pi
		return ret

	def dist(self, other):
		return math.sqrt((self.x - other.x) ** 2 + (self.y - other.y) ** 2)

	def __str__(self):
		return f'{self.x}, {self.y}'
(xs, ys, xt, yt) = list(map(int, input().split()))
N = int(input())
circles = [(Vec(xs, ys), 0)]
for _ in range(N):
	(x, y, r) = list(map(int, input().split()))
	circles.append((Vec(x, y), r))
circles.append((Vec(xt, yt), 0))
d = [[math.inf] * (N + 2) for _ in range(N + 2)]
for i in range(N + 2):
	for j in range(i, N + 2):
		tmp = max(0, circles[i][0].dist(circles[j][0]) - (circles[i][1] + circles[j][1]))
		d[i][j] = tmp
		d[j][i] = tmp
q = [(0, 0)]
visited = [False] * (N + 2)
ans = math.inf
while q:
	(c, i) = heapq.heappop(q)
	if visited[i]:
		continue
	if i == N + 1:
		print(c)
		return
	visited[i] = True
	for j in range(N + 2):
		if visited[j]:
			continue
		heapq.heappush(q, (c + d[i][j], j))


import sys
sys.setrecursionlimit(10000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15
from heapq import heapify, heappop, heappush

def dijkstra(G, s=0):
	n = len(G)
	dist = [INF] * n
	dist[s] = 0
	q = [(0, s)]
	while q:
		(d, v) = heappop(q)
		if dist[v] < d:
			continue
		for (e, cost) in G[v]:
			if dist[e] > dist[v] + cost:
				dist[e] = dist[v] + cost
				heappush(q, (dist[e], e))
	return dist
from math import hypot

def main():
	(sy, sx, gy, gx) = map(int, input().split())
	N = int(input())
	circles = [(sy, sx, 0)] + [tuple(map(int, input().split())) for _ in range(N)] + [(gy, gx, 0)]
	N += 2
	G = [[] for _ in range(N)]
	for i in range(N):
		(x, y, z) = circles[i]
		for j in range(i + 1, N):
			(p, q, r) = circles[j]
			d = max(0, hypot(x - p, y - q) - z - r)
			G[i].append((j, d))
			G[j].append((i, d))
	dist = dijkstra(G)
	ans = dist[-1]
	print(ans)
main()


import sys
read = sys.stdin.read
readline = sys.stdin.readline
(xs, ys, xt, yt) = map(int, readline().split())
(n,) = map(int, readline().split())
xyr = [tuple(map(int, readline().split())) for _ in range(n)] + [(xs, ys, 0), (xt, yt, 0)]
from heapq import *

def dijkstra(d, s0):
	n = len(d)
	INF = float('inf')
	dist = [INF] * n
	dist[s0] = 0.0
	res = d[s0][:]
	res[s0] = INF
	for _ in range(n - 1):
		idx = min(range(n), key=lambda i: res[i])
		r = dist[idx] = res[idx]
		res[idx] = INF
		for j in range(n):
			if res[j] != INF:
				res[j] = min(res[j], r + d[idx][j])
	return dist
from math import hypot
d = [[max(0.0, hypot(xi - xj, yi - yj) - ri - rj) for (xj, yj, rj) in xyr] for (xi, yi, ri) in xyr]
dist = dijkstra(d, n)
print(dist[-1])


def main():
	import heapq
	from sys import stdin
	input = stdin.readline
	(xs, ys, xt, yt) = map(int, input().split())
	n = int(input())
	xyr = [[xs, ys, 0], [xt, yt, 0]] + [list(map(int, input().split())) for _ in [0] * n]
	g = [[] for _ in [0] * (n + 2)]
	for i in range(n + 1):
		(x1, y1, r1) = xyr[i]
		for j in range(i + 1, n + 2):
			(x2, y2, r2) = xyr[j]
			d_temp = max(0, ((x1 - x2) ** 2 + (y1 - y2) ** 2) ** 0.5 - r1 - r2)
			g[i].append((j, d_temp))
			g[j].append((i, d_temp))
	d = [0] * (n + 2)
	visit = [False] * (n + 2)
	visit[0] = True
	h = []
	for (i, j) in g[0]:
		h.append((j, i))
	heapq.heapify(h)
	while h:
		(i, j) = heapq.heappop(h)
		if visit[j] == True:
			continue
		visit[j] = True
		d[j] = i
		for (k, l) in g[j]:
			if visit[k] == False:
				heapq.heappush(h, (l + i, k))
	print(d[1])
main()


from heapq import *
(xs, ys, xt, yt) = [int(_) for _ in input().split()]
N = int(input())
XYR = [[xs, ys, 0]] + [[int(_) for _ in input().split()] for _ in range(N)] + [[xt, yt, 0]]
G = [[0] * (N + 2) for _ in range(N + 2)]
for i in range(N + 1):
	for j in range(i + 1, N + 2):
		G[i][j] = G[j][i] = max(((XYR[i][0] - XYR[j][0]) ** 2 + (XYR[i][1] - XYR[j][1]) ** 2) ** 0.5 - XYR[i][2] - XYR[j][2], 0)

def dijkstra(V, G, start):
	INF = float('inf')
	D = [INF for _ in range(V)]
	D[start] = 0
	H = [(0, start)]
	while H:
		(du, u) = heappop(H)
		if D[u] < du:
			continue
		for (v, d) in enumerate(G[u]):
			if D[v] > du + d:
				D[v] = du + d
				heappush(H, (D[v], v))
	return D
D = dijkstra(N + 2, G, 0)
print(D[-1])


def examC():
	(N, x) = LI()
	A = LI()
	ans = 0
	cur = A[0]
	if A[0] > x:
		ans += A[0] - x
		cur = x
	for i in range(1, N):
		if cur + A[i] <= x:
			cur = A[i]
			continue
		ans += cur + A[i] - x
		cur = A[i] - (cur + A[i] - x)
	print(ans)
	return

def examD():
	S = SI()
	return

def dijkstra(edge_adj, node, start):
	dist = [inf] * node
	used = [False] * node
	dist[start] = 0
	while True:
		v = -1
		for i in range(node):
			if not used[i] and (v == -1 or dist[v] > dist[i]):
				v = i
		if v == -1:
			break
		used[v] = True
		for i in range(node):
			if dist[i] > dist[v] + edge_adj[v][i]:
				dist[i] = dist[v] + edge_adj[v][i]
	return dist

def examE():
	(xs, ys, xg, yg) = LI()
	N = I()
	XYR = [[] for _ in range(N)]
	for i in range(N):
		XYR[i] = LI()
	XYR.append([xs, ys, 0])
	XYR.append([xg, yg, 0])
	V = [[0] * (N + 2) for _ in range(N + 2)]
	for i in range(N + 2):
		for j in range(i + 1, N + 2):
			s = XYR[i]
			t = XYR[j]
			cur = ((s[0] - t[0]) ** 2 + (s[1] - t[1]) ** 2) ** 0.5 - (s[2] + t[2])
			V[i][j] = max(0, cur)
			V[j][i] = max(0, cur)
	D = dijkstra(V, N + 2, N)
	ans = D[-1]
	print(ans)
	return
import sys, copy, bisect, itertools, heapq, math
from heapq import heappop, heappush, heapify
from collections import Counter, defaultdict, deque

def I():
	return int(sys.stdin.readline())

def LI():
	return list(map(int, sys.stdin.readline().split()))

def LSI():
	return list(map(str, sys.stdin.readline().split()))

def LS():
	return sys.stdin.readline().split()

def SI():
	return sys.stdin.readline().strip()
global mod, inf
mod = 10 ** 9 + 7
inf = 10 ** 18
examE()


from heapq import heappush, heappop
from math import sqrt
from sys import stdin
input = stdin.buffer.readline

def main():
	(xs, ys, xt, yt) = map(int, input().split())
	n = int(input())
	xyr = [(0, 0, 0)] * (n + 2)
	xyr[0] = (xs, ys, 0)
	xyr[1] = (xt, yt, 0)
	for i in range(2, n + 2):
		(x, y, r) = map(int, input().split())
		xyr[i] = (x, y, r)
	heap = []
	heappush(heap, (0.0, 0))
	times = [10 ** 19] * (n + 2)
	times[0] = 0
	yet = set(range(n + 2))
	while True:
		(time, ind) = heappop(heap)
		if ind == 1:
			print(time)
			break
		if times[ind] == time:
			yet.remove(ind)
			(x, y, r) = xyr[ind]
			for i in yet:
				(xi, yi, ri) = xyr[i]
				new_time = max(sqrt((x - xi) * (x - xi) + (y - yi) * (y - yi)) - (r + ri), 0.0) + time
				if new_time < times[i]:
					times[i] = new_time
					heappush(heap, (new_time, i))
main()


from heapq import *
(sx, sy, tx, ty) = list(map(int, input().split()))
N = int(input())
circles = [tuple(map(int, input().split())) for _ in range(N)]
s = N
t = N + 1
adj_matrix = [[0] * (N + 2) for _ in range(N + 2)]
adj_matrix[s][t] = adj_matrix[t][s] = ((tx - sx) ** 2 + (ty - sy) ** 2) ** 0.5
for (v, (x, y, r)) in enumerate(circles):
	adj_matrix[s][v] = adj_matrix[v][s] = max(0, ((x - sx) ** 2 + (y - sy) ** 2) ** 0.5 - r)
	adj_matrix[t][v] = adj_matrix[v][t] = max(0, ((x - tx) ** 2 + (y - ty) ** 2) ** 0.5 - r)
for (v1, (x1, y1, r1)) in enumerate(circles):
	for (v2, (x2, y2, r2)) in enumerate(circles[v1 + 1:], start=v1 + 1):
		adj_matrix[v1][v2] = adj_matrix[v2][v1] = max(0, ((x1 - x2) ** 2 + (y1 - y2) ** 2) ** 0.5 - r1 - r2)
dp = [float('inf')] * (N + 2)
dp[t] = 0
pq = [(0, t)]
while pq:
	(cost, v) = heappop(pq)
	if dp[v] < cost:
		continue
	for (nv, dist) in enumerate(adj_matrix[v]):
		if dp[nv] > cost + dist:
			dp[nv] = cost + dist
			heappush(pq, (dp[nv], nv))
print(dp[s])


import sys
input = sys.stdin.readline
from collections import defaultdict
from heapq import heappop, heappush

class Graph(object):

	def __init__(self):
		self.graph = defaultdict(list)

	def add_edge(self, a, b, w):
		self.graph[a].append((b, w))

class Dijkstra(object):

	def __init__(self, graph, s):
		self.g = graph.graph
		self.dist = defaultdict(lambda : float('inf'))
		self.dist[s] = 0
		self.Q = []
		heappush(self.Q, (self.dist[s], s))
		while self.Q:
			(dist_u, u) = heappop(self.Q)
			if self.dist[u] < dist_u:
				continue
			for (v, w) in self.g[u]:
				alt = dist_u + w
				if self.dist[v] > alt:
					self.dist[v] = alt
					heappush(self.Q, (alt, v))

	def s_d(self, goal):
		return self.dist[goal]
(xs, ys, xg, yg) = list(map(int, input().split()))
xyr = []
xyr.append([xs, ys, 0])
N = int(input())
for i in range(N):
	xyr.append(list(map(int, input().split())))
xyr.append([xg, yg, 0])
g_a = Graph()
for i in range(N + 1):
	for j in range(i + 1, N + 2):
		R = (xyr[i][0] - xyr[j][0]) * (xyr[i][0] - xyr[j][0]) + (xyr[i][1] - xyr[j][1]) * (xyr[i][1] - xyr[j][1])
		R = R ** 0.5
		if R > xyr[i][2] + xyr[j][2]:
			r = R - xyr[i][2] - xyr[j][2]
		else:
			r = 0
		g_a.add_edge(i, j, r)
		g_a.add_edge(j, i, r)
d_a = Dijkstra(g_a, 0)
print(d_a.s_d(N + 1))


from struct import pack, unpack
import math
from heapq import heapify, heappush as hpush, heappop as hpop
(xs, ys, xt, yt) = map(int, input().split())
N = int(input())
X = [(xs, ys, 0), (xt, yt, 0)]
for _ in range(N):
	(x, y, r) = map(int, input().split())
	X.append((x, y, r))
N += 2
DD = [[0] * N for _ in range(N)]
for i in range(N):
	(xi, yi, ri) = X[i]
	for j in range(N):
		(xj, yj, rj) = X[j]
		DD[i][j] = max(math.sqrt((xi - xj) ** 2 + (yi - yj) ** 2) - (ri + rj), 0)

def dijkstra(n, E, i0=0):
	D = [1 << 40] * n
	D[i0] = 0
	Q = set([i for i in range(n)])
	while Q:
		d = 1 << 40
		for q in Q:
			if D[q] < d:
				i = q
				d = D[q]
		Q.remove(i)
		for (j, w) in enumerate(DD[i]):
			if j == i:
				continue
			nd = d + w
			if D[j] > nd:
				D[j] = nd
	return D
print(dijkstra(N, X)[1])


from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from functools import reduce
sys.setrecursionlimit(2147483647)
INF = 10 ** 13

def LI():
	return list(map(int, sys.stdin.buffer.readline().split()))

def I():
	return int(sys.stdin.buffer.readline())

def LS():
	return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()

def S():
	return sys.stdin.buffer.readline().rstrip().decode('utf-8')

def IR(n):
	return [I() for i in range(n)]

def LIR(n):
	return [LI() for i in range(n)]

def SR(n):
	return [S() for i in range(n)]

def LSR(n):
	return [LS() for i in range(n)]

def SRL(n):
	return [list(S()) for i in range(n)]

def MSRL(n):
	return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007
(sx, sy, gx, gy) = LI()
n = I()
circles = [[sx, sy, 0]] + LIR(n) + [[gx, gy, 0]]
G = [[0] * (n + 2) for _ in range(n + 2)]
for i in range(n + 2):
	for j in range(i + 1, n + 2):
		G[i][j] = G[j][i] = max(0, ((circles[i][0] - circles[j][0]) ** 2 + (circles[i][1] - circles[j][1]) ** 2) ** 0.5 - circles[i][2] - circles[j][2])

def dijkstra(graph, start=0):
	que = [(0, start)]
	dist = [INF] * (n + 2)
	dist[start] = 0
	while que:
		(min_dist, u) = heappop(que)
		if min_dist > dist[u]:
			continue
		for (v, c) in enumerate(graph[u]):
			if dist[u] + c < dist[v]:
				dist[v] = dist[u] + c
				heappush(que, (dist[u] + c, v))
	return dist
print(dijkstra(G, start=0)[-1])


from scipy.sparse.csgraph import dijkstra, csgraph_from_dense
(xs, ys, xg, yg) = map(int, input().split())
N = int(input())
xyr = [(xs, ys, 0)]
xyr.extend([list(map(int, input().split())) for i in range(N)])
xyr.append((xg, yg, 0))
graph = [[0] * (N + 2) for _ in range(N + 2)]
max_val = 10 ** 9
for i in range(N + 2):
	graph[i][i] = max_val
for i in range(N + 2):
	for j in range(i + 1, N + 2):
		(x1, y1, r1) = xyr[i]
		(x2, y2, r2) = xyr[j]
		d = max(0, ((x1 - x2) ** 2 + (y1 - y2) ** 2) ** 0.5 - r1 - r2)
		graph[i][j] = graph[j][i] = d
g = csgraph_from_dense(graph, null_value=max_val)
print(dijkstra(g, indices=0)[-1])


(sx, sy, tx, ty) = map(int, input().split())
raw = [[sx, sy, 0]]
n = int(input()) + 2
for _ in range(n - 2):
	raw.append(list(map(int, input().split())))
raw.append([tx, ty, 0])
dist = []
for i in range(n):
	add = []
	for j in range(n):
		tmp = (raw[i][0] - raw[j][0]) ** 2 + (raw[i][1] - raw[j][1]) ** 2
		tmp **= 0.5
		tmp -= raw[i][2] + raw[j][2]
		if tmp < 0:
			tmp = 0
		add.append(tmp)
	dist.append(add)
inf = 10 ** 12
now = []
for i in range(n):
	now.append([dist[0][i], i])
now[0][0] = inf
for _ in range(n - 1):
	(d, j) = min(now)
	if j == n - 1:
		print(d)
	now[j][0] = inf
	for i in range(n):
		if now[i][0] == inf:
			continue
		if now[i][0] > d + dist[i][j]:
			now[i][0] = d + dist[i][j]


import typing
import sys
import math
import collections
import bisect
import itertools
import heapq
import decimal
import copy
import operator
INF = 10 ** 20
MOD = 10 ** 9 + 7

def ni():
	return int(sys.stdin.readline())

def ns():
	return list(map(int, sys.stdin.readline().split()))

def na():
	return list(map(int, sys.stdin.readline().split()))

def na1():
	return list([int(x) - 1 for x in sys.stdin.readline().split()])

def dist(l1, l2):
	return max(0, math.sqrt((l1[0] - l2[0]) ** 2 + (l1[1] - l2[1]) ** 2) - l1[2] - l2[2])

def main():
	(xs, ys, xt, yt) = ns()
	n = ni()
	pos = [na() for _ in range(n)]
	pos.insert(0, [xs, ys, 0])
	pos.append([xt, yt, 0])
	d = [[dist(pos[i], pos[j]) for i in range(n + 2)] for j in range(n + 2)]
	mind = [INF for _ in range(n + 2)]
	visited = [False for _ in range(n + 2)]
	hq = []
	heapq.heappush(hq, (0, 0))
	mind[0] = 0
	while hq:
		(dis, idx) = heapq.heappop(hq)
		if visited[idx]:
			continue
		visited[idx] = True
		if idx == n + 1:
			break
		for i in range(n + 2):
			if i == idx:
				continue
			ndist = dis + d[idx][i]
			if ndist < mind[i] and ndist < mind[n + 1]:
				mind[i] = ndist
				heapq.heappush(hq, (ndist, i))
	print(mind[n + 1])

def __starting_point():
	main()
__starting_point()


class Dijkstra:

	class Edge:

		def __init__(self, _to, _cost):
			self.to = _to
			self.cost = _cost

	def __init__(self, V):
		self.G = [[] for i in range(V)]
		self._E = 0
		self._V = V

	def E(self):
		return self._E

	def V(self):
		return self._V

	def add(self, _from, _to, _cost):
		self.G[_from].append(self.Edge(_to, _cost))
		self._E += 1

	def shortest_path(self, s):
		import heapq
		que = []
		d = [float('inf')] * self._V
		d[s] = 0
		heapq.heappush(que, (0, s))
		while que:
			(cost, v) = heapq.heappop(que)
			if d[v] < cost:
				continue
			for i in range(len(self.G[v])):
				e = self.G[v][i]
				if d[e.to] > d[v] + e.cost:
					d[e.to] = d[v] + e.cost
					heapq.heappush(que, (d[e.to], e.to))
		return d
import sys
input = sys.stdin.readline
(xs, ys, xt, yt) = map(int, input().split())
n = int(input())
xyr = [list(map(int, input().split())) for i in range(n)]
graph = [[10 ** 9] * (n + 2) for i in range(n + 2)]
graph[0][n + 1] = graph[n + 1][0] = ((xs - xt) ** 2 + (ys - yt) ** 2) ** 0.5
for i in range(1, n + 1):
	for j in range(1, n + 1):
		d = ((xyr[i - 1][0] - xyr[j - 1][0]) ** 2 + (xyr[i - 1][1] - xyr[j - 1][1]) ** 2) ** 0.5
		graph[i][j] = graph[j][i] = max(0, d - xyr[i - 1][2] - xyr[j - 1][2])
for i in range(1, n + 1):
	d1 = ((xs - xyr[i - 1][0]) ** 2 + (ys - xyr[i - 1][1]) ** 2) ** 0.5
	d2 = ((xt - xyr[i - 1][0]) ** 2 + (yt - xyr[i - 1][1]) ** 2) ** 0.5
	graph[0][i] = graph[i][0] = max(0, d1 - xyr[i - 1][2])
	graph[n + 1][i] = graph[i][n + 1] = max(0, d2 - xyr[i - 1][2])
d = Dijkstra(n + 2)
for i in range(n + 2):
	for j in range(n + 2):
		d.add(i, j, graph[i][j])
print(d.shortest_path(0)[n + 1])


(xs, ys, xt, yt) = map(int, input().split())
N = int(input())
L = [[xs, ys, 0], [xt, yt, 0]]
for _ in range(N):
	L.append(list(map(int, input().split())))
V = N + 2
G = [[] for _ in range(N + 2)]
s = 0
for i in range(N + 2):
	for j in range(N + 2):
		if i != j:
			G[i].append([j, max(0, ((L[i][0] - L[j][0]) ** 2 + (L[i][1] - L[j][1]) ** 2) ** 0.5 - (L[i][2] + L[j][2]))])
INF = float('inf')
import heapq

def dijkstra(s):
	d = [INF for _ in range(V)]
	d[s] = 0
	que = []
	heapq.heappush(que, (0, s))
	while len(que) != 0:
		p = heapq.heappop(que)
		v = p[1]
		if d[v] < p[0]:
			continue
		for i in range(len(G[v])):
			e = G[v][i]
			if d[e[0]] > d[v] + e[1]:
				d[e[0]] = d[v] + e[1]
				heapq.heappush(que, (d[e[0]], e[0]))
	return d
d = dijkstra(0)
print(d[1])


(xs, ys, xg, yg) = map(int, input().split())
n = int(input())
xyr = [list(map(int, input().split())) for i in range(n)]
import math
from collections import defaultdict
link = defaultdict(list)
dist = math.sqrt((xs - xg) ** 2 + (ys - yg) ** 2)
link[10000].append([20000, dist])
for i in range(n):
	(x, y, r) = xyr[i]
	dist = math.sqrt((x - xs) ** 2 + (y - ys) ** 2) - r
	dist = max(0, dist)
	link[10000].append([i, dist])
	dist = math.sqrt((x - xg) ** 2 + (y - yg) ** 2) - r
	dist = max(0, dist)
	link[i].append([20000, dist])
for i in range(n):
	for j in range(i + 1, n):
		(x1, y1, r1) = xyr[i]
		(x2, y2, r2) = xyr[j]
		dist = math.sqrt((x1 - x2) ** 2 + (y1 - y2) ** 2) - r1 - r2
		dist = max(0, dist)
		link[i].append([j, dist])
		link[j].append([i, dist])
from heapq import heappush, heappop, heappushpop, heapify
from collections import defaultdict

def dks(g, start):
	visited = set()
	hq = []
	heappush(hq, (0, start))
	cost = defaultdict(lambda : float('inf'))
	while hq:
		(shortest, i) = heappop(hq)
		if i in visited:
			continue
		visited.add(i)
		cost[i] = shortest
		for (j, t) in g[i]:
			if j in visited:
				continue
			heappush(hq, (shortest + t, j))
	return cost
res = dks(link, 10000)
print(res[20000])


import sys
input = sys.stdin.readline
(Xs, Ys, Xg, Yg) = map(int, input().split())
N = int(input())
L = []
L.append([Xs, Ys, 0])
for i in range(N):
	(x, y, r) = map(int, input().split())
	L.append([x, y, r])
L.append([Xg, Yg, 0])
cost = [[-1 for i in range(N + 2)] for j in range(N + 2)]
for i in range(N + 2):
	for j in range(i, N + 2):
		cost[i][j] = max(0, ((L[i][0] - L[j][0]) ** 2 + (L[i][1] - L[j][1]) ** 2) ** 0.5 - L[i][2] - L[j][2])
		cost[j][i] = cost[i][j]

def jdijkstra(s, n, w, cost):
	d = [float('inf')] * n
	used = [False] * n
	d[s] = 0
	while True:
		v = -1
		for i in range(n):
			if not used[i] and v == -1:
				v = i
			elif not used[i] and d[i] < d[v]:
				v = i
		if v == -1:
			break
		used[v] = True
		for j in range(n):
			d[j] = min(d[j], d[v] + cost[v][j])
	return d
ans = jdijkstra(0, N + 2, (N + 2) ** 2, cost)
print(ans[-1])


(xs, ys, xt, yt) = list(map(int, input().split()))
N = int(input())
a = []
for i in range(N):
	a.append(list(map(int, input().split())))

class Dijkstra(object):

	def __init__(self, distancemap, start):
		self.start = start
		self.size = len(distancemap)
		self.distance = [float('inf') for x in range(self.size)]
		self.distance[start] = 0
		self.prev = [0 for x in range(self.size)]
		self.prev[start] = -1
		yet = list(range(self.size))
		yet.remove(start)
		now = start
		while yet != []:
			nearest_num = 0
			nearest_dis = float('inf')
			for i in yet:
				total_dis = distancemap[now][i] + self.distance[now]
				self.distance[i] = min(total_dis, self.distance[i])
				if self.distance[i] <= nearest_dis:
					nearest_dis = self.distance[i]
					nearest_num = i
			yet.remove(nearest_num)
			self.prev[nearest_num] = now
			now = nearest_num

	def route(self, goal):
		route = []
		while True:
			route.append(self.prev[goal])
			goal = self.prev[goal]
			if goal == self.start:
				break
		route.reverse()
		return route
import math

def solve(xs, ys, xt, yt, N, a):
	a.insert(0, [xs, ys, 0])
	a.append([xt, yt, 0])

	def distance(i, j):
		x1 = a[i][0]
		y1 = a[i][1]
		r1 = a[i][2]
		x2 = a[j][0]
		y2 = a[j][1]
		r2 = a[j][2]
		d = math.sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)) - r1 - r2
		if d < 0:
			d = 0
		return d
	distancemap = [[0 for x in range(N + 2)] for x in range(N + 2)]
	for i in range(N + 2):
		for j in range(N + 2):
			if i > j:
				distancemap[i][j] = distancemap[j][i]
			else:
				distancemap[i][j] = distance(i, j)
	d = Dijkstra(distancemap, 0)
	return d.distance.pop()
print(solve(xs, ys, xt, yt, N, a))


import sys
input = sys.stdin.readline
inf = float('inf')

def dijkstra(s):
	d = [inf] * N
	used = [False] * N
	d[s] = 0
	while True:
		v = -1
		for i in range(N):
			if not used[i] and v == -1:
				v = i
			elif not used[i] and d[i] < d[v]:
				v = i
		if v == -1:
			break
		used[v] = True
		for j in range(N):
			d[j] = min(d[j], d[v] + cost[v][j])
	return d
(xs, ys, xt, yt) = map(int, input().split())
N = int(input())
p = list()
p.append((xs, ys, 0))
p.append((xt, yt, 0))
for _ in range(N):
	p.append(tuple(map(int, input().split())))
cost = [[0] * (N + 2) for _ in range(N + 2)]
for i in range(N + 2):
	for j in range(i, N + 2):
		cost[i][j] = cost[j][i] = max(((p[i][0] - p[j][0]) ** 2 + (p[i][1] - p[j][1]) ** 2) ** 0.5 - p[i][2] - p[j][2], 0)
cost = tuple(cost)
N += 2
res = dijkstra(0)
print(res[1])


import heapq
(xs, ys, xt, yt) = map(int, input().split())
N = int(input())
L = [[int(l) for l in input().split()] for _ in range(N)]

def dist(x, y, s, t):
	return ((x - s) ** 2 + (y - t) ** 2) ** 0.5
h = []
for i in range(N):
	heapq.heappush(h, (max(0, dist(xs, ys, L[i][0], L[i][1]) - L[i][2]), i))
inf = 10 ** 10
d = [inf] * N
cnt = 0
while cnt < N:
	temp = heapq.heappop(h)
	if d[temp[1]] < inf:
		continue
	cnt += 1
	d[temp[1]] = temp[0]
	for i in range(N):
		if d[i] < inf:
			continue
		heapq.heappush(h, (temp[0] + max(0, dist(L[i][0], L[i][1], L[temp[1]][0], L[temp[1]][1]) - L[i][2] - L[temp[1]][2]), i))
ans = dist(xs, ys, xt, yt)
for i in range(N):
	ans = min(ans, d[i] + max(0, dist(xt, yt, L[i][0], L[i][1]) - L[i][2]))
print(ans)


from math import sqrt
from collections import defaultdict as dd

class dijkstra:

	def __init__(self, n, e):
		self.e = e
		self.n = n

	def path(self, s, t):
		d = [float('inf')] * (self.n + 1)
		vis = set()
		d[s] = 0
		while not t in vis:
			v = -1
			for i in range(self.n):
				if not i in vis and v == -1:
					v = i
				elif not i in vis and d[i] < d[v]:
					v = i
			if v == -1:
				break
			vis.add(v)
			for p in self.e[v]:
				d[p[0]] = min(d[p[0]], d[v] + p[1])
		return d[t]

def distance(u1, v1, r1, u2, v2, r2):
	dis = sqrt((u1 - u2) ** 2 + (v1 - v2) ** 2)
	return max(dis - r1 - r2, 0)
(sx, sy, tx, ty) = map(int, input().split())
N = int(input())
c = [list(map(int, input().split())) for _ in range(N)]
c.append([sx, sy, 0])
c.append([tx, ty, 0])
e = dd(list)
for i in range(N + 1):
	for j in range(N + 2):
		if i == j:
			continue
		if j == N:
			continue
		e[i + 1].append([j + 1, distance(c[i][0], c[i][1], c[i][2], c[j][0], c[j][1], c[j][2])])
d = dijkstra(N + 2, e)
print(d.path(N + 1, N + 2))


import sys
input = sys.stdin.readline
from heapq import heappop, heappush
import math
(xs, ys, xt, yt) = map(int, input().split())
n = int(input())
v = [[xs, ys, 0]]
for _ in range(n):
	(x, y, r) = map(int, input().split())
	v.append([x, y, r])
v.append([xt, yt, 0])

def dd(a, b):
	return max(0, math.sqrt((a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2) - a[2] - b[2])
edges = [[0] * (n + 2) for _ in range(n + 2)]
for i in range(n + 2):
	for j in range(i + 1, n + 2):
		edges[i][j] = dd(v[i], v[j])
		edges[j][i] = dd(v[i], v[j])

def dijkstra(s, n, edges):
	d = [float('inf') for _ in range(n)]
	d[s] = 0
	q = [(0, s)]
	while q:
		(dist_u, u) = heappop(q)
		if d[u] < dist_u:
			continue
		for (v, c) in enumerate(edges[u]):
			if d[v] > dist_u + c:
				d[v] = dist_u + c
				heappush(q, (d[v], v))
	return d
ans = dijkstra(0, n + 2, edges)
print(ans[n + 1])


from heapq import heappush, heappop
from math import sqrt
(xs, ys, xt, yt) = map(int, input().split())
N = int(input())
xyr = [[int(i) for i in input().split()] for _ in range(N)]
cost = [0] * N
h = []

def dist(x, y):
	return sqrt(x ** 2 + y ** 2)
for (i, (x, y, r)) in enumerate(xyr):
	d = max(0, dist(xs - x, ys - y) - r)
	heappush(h, (d, i))
	cost[i] = d
while h:
	(dc, i) = heappop(h)
	if cost[i] < dc:
		continue
	(xc, yc, rc) = xyr[i]
	for (i, (x, y, r)) in enumerate(xyr):
		d = dc + max(0, dist(xc - x, yc - y) - rc - r)
		if d < cost[i]:
			heappush(h, (d, i))
			cost[i] = d
ret = sqrt((xs - xt) ** 2 + (ys - yt) ** 2)
for (i, (x, y, r)) in enumerate(xyr):
	ret = min(ret, cost[i] + max(0, dist(xt - x, yt - y) - r))
print(ret)


(xs, ys, xt, yt) = map(int, input().split())
N = int(input())
XYR = [list(map(int, input().split())) for _ in [0] * N]
XYR.append([xs, ys, 0])
XYR.append([xt, yt, 0])
E = [{} for _ in [0] * (N + 2)]
for i in range(N + 2):
	for j in range(N + 2):
		if j == i:
			continue
		dx = XYR[i][0] - XYR[j][0]
		dy = XYR[i][1] - XYR[j][1]
		r2 = XYR[i][2] + XYR[j][2]
		E[i][j] = max(0, (dx ** 2 + dy ** 2) ** 0.5 - r2)
import heapq

def Dijkstra(N, E, start):
	d = [-1] * N
	q = [(0, start)]
	while q:
		(ci, i) = heapq.heappop(q)
		if d[i] != -1:
			continue
		d[i] = ci
		for (j, cj) in E[i].items():
			if d[j] != -1:
				continue
			heapq.heappush(q, (ci + cj, j))
	return d
print(Dijkstra(N + 2, E, N)[-1])


from math import sqrt
from sys import stdin
input = stdin.buffer.readline

def main():
	(xs, ys, xt, yt) = map(int, input().split())
	n = int(input())
	xyr = [(0, 0, 0)] * (n + 2)
	xyr[0] = (xs, ys, 0)
	xyr[1] = (xt, yt, 0)
	for i in range(2, n + 2):
		(x, y, r) = map(int, input().split())
		xyr[i] = (x, y, r)
	inf = float('inf')
	dic = {i: inf for i in range(n + 2)}
	dic[0] = 0.0
	while True:
		(ind, cost) = min(dic.items(), key=lambda x: x[1])
		dic.pop(ind)
		if ind == 1:
			print(cost)
			break
		(x, y, r) = xyr[ind]
		for (i, old_cost) in dic.items():
			(xi, yi, ri) = xyr[i]
			new_cost = max(sqrt((x - xi) * (x - xi) + (y - yi) * (y - yi)) - (r + ri), 0.0) + cost
			if new_cost < old_cost:
				dic[i] = new_cost
main()


import math
from heapq import heappush, heappop

def main():
	(sx, sy, gx, gy) = map(int, input().split())
	N = int(input())
	P = [(sx, sy, 0)] + [(gx, gy, 0)] + [tuple(map(int, input().split())) for _ in range(N)]
	dist = [[0] * (N + 2) for _ in range(N + 2)]
	for i in range(N + 2):
		for j in range(N + 2):
			(xi, yi, ri) = P[i]
			(xj, yj, rj) = P[j]
			dist[i][j] = max(math.sqrt((xi - xj) ** 2 + (yi - yj) ** 2) - (ri + rj), 0.0)
	INF = float('Inf')
	ans = [INF] * (N + 2)
	h = [(0.0, 0)]
	while len(h) and ans[1] == INF:
		(d, i) = heappop(h)
		if ans[i] != INF:
			continue
		ans[i] = d
		for j in range(N + 2):
			if ans[j] == INF:
				heappush(h, (d + dist[i][j], j))
	print(ans[1])
main()


inf = 10 ** 18

def D(a, b, c, d):
	return ((c - a) ** 2 + (d - b) ** 2) ** 0.5
(xs, ys, xt, yt) = map(int, input().split())
n = int(input())
xyr = [(xs, ys, 0)]
for i in range(n):
	xyr.append(tuple(map(int, input().split())))
xyr.append((xt, yt, 0))
dis = [[inf] * (n + 2) for i in range(n + 2)]
for i in range(n + 2):
	dis[i][i] = 0
for i in range(n + 2):
	for j in range(i):
		(a, b, r1) = xyr[i]
		(c, d, r2) = xyr[j]
		r = D(a, b, c, d) - (r1 + r2)
		r = max(0, r)
		dis[i][j] = r
		dis[j][i] = r
cost = [inf] * (n + 2)
cost[0] = 0
visited = [0] * (n + 2)
now = 0
for i in range(n + 2):
	visited[now] = 1
	MIN = inf
	pre_now = -1
	for j in range(n + 2):
		if visited[j] == 0:
			cost[j] = min(cost[now] + dis[now][j], cost[j])
			if MIN > cost[j]:
				MIN = cost[j]
				pre_now = j
	now = pre_now
print(cost[n + 1])


import sys
from math import hypot

def input():
	return sys.stdin.readline().strip()

def list2d(a, b, c):
	return [[c] * b for i in range(a)]

def list3d(a, b, c, d):
	return [[[d] * c for j in range(b)] for i in range(a)]

def list4d(a, b, c, d, e):
	return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]

def ceil(x, y=1):
	return int(-(-x // y))

def INT():
	return int(input())

def MAP():
	return map(int, input().split())

def LIST(N=None):
	return list(MAP()) if N is None else [INT() for i in range(N)]

def Yes():
	print('Yes')

def No():
	print('No')

def YES():
	print('YES')

def NO():
	print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def dijkstra(N: int, nodes: list, src: int) -> list:
	from heapq import heappush, heappop
	res = [INF] * N
	que = [(0, src)]
	res[src] = 0
	while len(que) != 0:
		(dist, cur) = heappop(que)
		if res[cur] < dist:
			continue
		for (nxt, cost) in nodes[cur]:
			if dist + cost < res[nxt]:
				res[nxt] = dist + cost
				heappush(que, (dist + cost, nxt))
	return res
(sx, sy, tx, ty) = MAP()
N = INT()
XYR = []
for i in range(N):
	(x, y, r) = MAP()
	XYR.append((x, y, r))
XYR.append((sx, sy, 0))
XYR.append((tx, ty, 0))
N += 2
nodes = [[] for i in range(N)]
for i in range(N):
	(x1, y1, r1) = XYR[i]
	for j in range(i + 1, N):
		(x2, y2, r2) = XYR[j]
		dist = hypot(x1 - x2, y1 - y2)
		cost = max(dist - (r1 + r2), 0)
		nodes[i].append((j, cost))
		nodes[j].append((i, cost))
res = dijkstra(N, nodes, N - 2)
print(res[N - 1])


from math import sqrt
from heapq import heappush, heappop
INF = float('inf')

def Dijkstra(barriers, vSt):
	numV = len(barriers)
	rests = set(range(numV))
	costs = [INF] * numV
	costs[vSt] = 0
	PQ = []
	heappush(PQ, (0, vSt))
	while PQ:
		(c, vNow) = heappop(PQ)
		if c > costs[vNow]:
			continue
		rests.remove(vNow)
		if not rests:
			break
		costNow = c
		(xi, yi, ri) = barriers[vNow]
		for v2 in rests:
			(xj, yj, rj) = barriers[v2]
			wt = sqrt((xj - xi) ** 2 + (yj - yi) ** 2) - ri - rj
			if wt < 0:
				wt = 0
			c2 = costNow + wt
			if c2 < costs[v2]:
				costs[v2] = c2
				heappush(PQ, (c2, v2))
	return costs
(xs, ys, xt, yt) = map(int, input().split())
N = int(input())
barriers = [(xs, ys, 0), (xt, yt, 0)] + [tuple(map(int, input().split())) for _ in range(N)]
costs = Dijkstra(barriers, 0)
print(costs[1])


import sys
sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7

def dijkstra(n, s, cost):
	res = [f_inf] * n
	res[s] = 0
	checked = [False] * n
	while True:
		v = -1
		for k in range(n):
			if not checked[k] and v == -1:
				v = k
			elif not checked[k] and res[k] < res[v]:
				v = k
		if v == -1:
			break
		checked[v] = True
		for m in range(n):
			res[m] = min(res[m], res[v] + cost[v][m])
	return res

def resolve():

	def calc_dist(x1, y1, x2, y2):
		return pow(pow(x1 - x2, 2) + pow(y1 - y2, 2), 0.5)
	(sx, sy, gx, gy) = list(map(int, input().split()))
	n = int(input())
	node = [[sx, sy, 0]] + [list(map(int, input().split())) for _ in range(n)] + [[gx, gy, 0]]
	cost = [[0] * (n + 2) for _ in range(n + 2)]
	for i in range(n + 2):
		(x1, y1, r1) = node[i]
		for j in range(i + 1, n + 2):
			(x2, y2, r2) = node[j]
			dist = max(0, calc_dist(x1, y1, x2, y2) - (r1 + r2))
			cost[i][j] = dist
			cost[j][i] = dist
	res = dijkstra(n + 2, 0, cost)
	print(res[-1])

def __starting_point():
	resolve()
__starting_point()


from math import hypot

def dijkstra(s, n, cost):
	d = [float('inf')] * n
	used = [False] * n
	d[s] = 0
	while True:
		v = -1
		for i in range(n):
			if not used[i] and v == -1:
				v = i
			elif not used[i] and d[i] < d[v]:
				v = i
		if v == -1:
			break
		used[v] = True
		for j in range(n):
			d[j] = min(d[j], d[v] + cost[v][j])
	return d
(xs, ys, xt, yt, n, *t) = map(int, open(0).read().split())
e = [(xs, ys, 0)] + list(zip(t[::3], t[1::3], t[2::3])) + [(xt, yt, 0)]
cost = tuple(([float('inf')] * (n + 2) for i in range(n + 2)))
for (i, (x, y, z)) in enumerate(e):
	for (j, (a, b, c)) in enumerate(e):
		cost[i][j] = max(0, hypot(x - a, y - b) - z - c)
print(dijkstra(0, n + 2, cost)[-1])


import math
import itertools
INVALID = -1
INF = 10 ** 12

def dijkstra_dense(num_vs, adj_matrix, source, dest):
	dist = [INF for _ in range(num_vs)]
	visited = [False for _ in range(num_vs)]
	dist[source] = 0
	while True:
		u = min((j for j in range(num_vs) if not visited[j]), key=lambda i: dist[i], default=INVALID)
		if u == INVALID or dist[u] == INF:
			break
		visited[u] = True
		for v in range(num_vs):
			w = adj_matrix[u][v]
			if u != v and w < INF:
				new_len = dist[u] + w
				if new_len < dist[v]:
					dist[v] = new_len
	return dist[dest]

def main():
	(x0, y0, xf, yf) = (int(x) for x in input().split())
	n = int(input())
	xs = [None for _ in range(n + 2)]
	ys = [None for _ in range(n + 2)]
	rs = [None for _ in range(n + 2)]
	(xs[0], ys[0], rs[0]) = (x0, y0, 0)
	(xs[n + 1], ys[n + 1], rs[n + 1]) = (xf, yf, 0)
	for i in range(1, n + 1):
		(xs[i], ys[i], rs[i]) = (int(z) for z in input().split())
	adj_matrix = [[INF for _ in range(n + 2)] for _ in range(n + 2)]
	for (i, j) in itertools.product(range(n + 2), repeat=2):
		adj_matrix[i][j] = max(0, math.hypot(xs[i] - xs[j], ys[i] - ys[j]) - (rs[i] + rs[j]))
	res = dijkstra_dense(n + 2, adj_matrix, 0, n + 1)
	print('{:.12f}'.format(res))
main()