stablegradients/pie-gem5-bysrc huggingface dataset:
// Original C++ solution (slower):
#include <cstdio>

#include <queue>

#include <cmath>

#include <limits>



using namespace std;



int x[1002], y[1002], r[1002];

double cost[1002][1002];

double d[1002];



double norm(double x1, double x2)

{

    double d = x1 - x2;

    return d * d;

}



int main()

{

    scanf("%d%d%d%d", &x[0], &y[0], &x[1], &y[1]);

    r[0] = r[1] = 0;



    int N;

    scanf("%d", &N);

    N += 2;

    for (int i = 2; i < N; i++) {

        scanf("%d%d%d", &x[i], &y[i], &r[i]);

    }



    for (int i = 0; i < N; i++) {

        for (int j = 0; j < N; j++) {

            cost[i][j] = max(sqrt(norm(x[i], x[j]) +  norm(y[i], y[j])) - r[i] - r[j], 0.0);

        }

    }



    d[0] = 0;

    for (int i = 1; i < N; i++)

        d[i] = numeric_limits<double>::max();



    priority_queue<pair<double, int>, vector<pair<double, int>>, greater<pair<double, int>>> pq;

    pq.push(make_pair(d[0], 0));



    while (!pq.empty()) {

        auto p = pq.top();

        pq.pop();

        int v = p.second;

        if (d[v] < p.first)

            continue;

        for (int i = 0; i < N; i++) {

            if (d[i] > d[v] + cost[v][i]) {

                d[i] = d[v] + cost[v][i];

                pq.push(make_pair(d[i], i));

            }

        }

    }



    printf("%.10f\n", d[1]);

}


// Optimized solution to the same problem (faster):
#include <cstdio>

#include <cmath>

#include <queue>

#include <limits>

using namespace std;



typedef pair<double, int> P;



int x[1002], y[1002], r[1002];

double cost[1002][1002];

bool fixed[1002];

double d[1002];



int main()

{

    scanf("%d%d%d%d", &x[0], &y[0], &x[1], &y[1]);

    r[0] = r[1] = 0;



    int N;

    scanf("%d", &N);

    N += 2;

    for (int i = 2; i < N; i++)

        scanf("%d%d%d", &x[i], &y[i], &r[i]);



    for (int i = 0; i < N; i++)

        for (int j = 0; j < N; j++)

            cost[i][j] = max(hypot(x[i] - x[j], y[i] - y[j]) - r[i] - r[j], 0.);



    fill(fixed, fixed + N, false);

    fill(d, d + N, numeric_limits<double>::infinity());

    d[0] = 0;

    while (true) {

        int v = -1;

        for (int i = 0; i < N; i++) {

            if (!fixed[i] && (v == -1 || d[i] < d[v]))

                v = i;

        }

        if (v == -1)

            break;

        fixed[v] = true;

        for (int i = 0; i < N; i++) {

            d[i] = min(d[i], d[v] + cost[v][i]);

        }

    }



    printf("%.12f\n", d[1]);

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <cstdio>

#include <cmath>

#include <queue>

#include <limits>

using namespace std;



typedef pair<double, int> P;



int x[1002], y[1002], r[1002];

double cost[1002][1002];

double d[1002];



int main()

{

    scanf("%d%d%d%d", &x[0], &y[0], &x[1], &y[1]);

    r[0] = r[1] = 0;



    int N;

    scanf("%d", &N);

    N += 2;

    for (int i = 2; i < N; i++)

        scanf("%d%d%d", &x[i], &y[i], &r[i]);



    for (int i = 0; i < N; i++)

        for (int j = 0; j < N; j++)

            cost[i][j] = max(hypot(x[i] - x[j], y[i] - y[j]) - r[i] - r[j], 0.);



    for (double &nd : d)

        nd = numeric_limits<double>::infinity();

    d[0] = 0;

    priority_queue<P> q;

    q.push(P(0, 0));



    while (!q.empty()) {

        auto p = q.top();

        double nowd = -p.first;

        int v = p.second;

        q.pop();

        if (nowd < d[v])

            continue;

        for (int i = 0; i < N; i++) {

            double nextd = d[v] + cost[v][i];

            if (d[i] > nextd) {

                d[i] = nextd;

                q.push(P(-nextd, i));

            }

        }

    }



    printf("%.12f\n", d[1]);

}


// Optimized solution to the same problem (faster):
#include <cstdio>

#include <cmath>

#include <queue>

#include <limits>

using namespace std;



typedef pair<double, int> P;



int x[1002], y[1002], r[1002];

double cost[1002][1002];

bool fixed[1002];

double d[1002];



int main()

{

    scanf("%d%d%d%d", &x[0], &y[0], &x[1], &y[1]);

    r[0] = r[1] = 0;



    int N;

    scanf("%d", &N);

    N += 2;

    for (int i = 2; i < N; i++)

        scanf("%d%d%d", &x[i], &y[i], &r[i]);



    for (int i = 0; i < N; i++)

        for (int j = 0; j < N; j++)

            cost[i][j] = max(hypot(x[i] - x[j], y[i] - y[j]) - r[i] - r[j], 0.);



    fill(fixed, fixed + N, false);

    fill(d, d + N, numeric_limits<double>::infinity());

    d[0] = 0;

    while (true) {

        int v = -1;

        for (int i = 0; i < N; i++) {

            if (!fixed[i] && (v == -1 || d[i] < d[v]))

                v = i;

        }

        if (v == -1)

            break;

        fixed[v] = true;

        for (int i = 0; i < N; i++) {

            d[i] = min(d[i], d[v] + cost[v][i]);

        }

    }



    printf("%.12f\n", d[1]);

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <cstdio>

#include <cmath>

#include <queue>

#include <limits>

using namespace std;



typedef pair<double, int> P;



int x[1002], y[1002], r[1002];

double cost[1002][1002];

double d[1002];



int main()

{

    scanf("%d%d%d%d", &x[0], &y[0], &x[1], &y[1]);

    r[0] = r[1] = 0;



    int N;

    scanf("%d", &N);

    N += 2;

    for (int i = 2; i < N; i++)

        scanf("%d%d%d", &x[i], &y[i], &r[i]);



    for (int i = 0; i < N; i++)

        for (int j = 0; j < N; j++)

            cost[i][j] = max(hypot(x[i] - x[j], y[i] - y[j]) - r[i] - r[j], 0.);



    for (double &nd : d)

        nd = numeric_limits<double>::infinity();

    d[0] = 0;

    priority_queue<P, vector<P>, greater<P>> q;

    q.push(P(0, 0));



    while (!q.empty()) {

        auto p = q.top();

        double nowd = p.first;

        int v = p.second;

        q.pop();

        if (nowd < d[v])

            continue;

        for (int i = 0; i < N; i++) {

            double nextd = d[v] + cost[v][i];

            if (d[i] > nextd) {

                d[i] = nextd;

                q.push(P(nextd, i));

            }

        }

    }



    printf("%.12f\n", d[1]);

}


// Optimized solution to the same problem (faster):
#include <cstdio>

#include <cmath>

#include <queue>

#include <limits>

using namespace std;



typedef pair<double, int> P;



int x[1002], y[1002], r[1002];

double cost[1002][1002];

bool fixed[1002];

double d[1002];



int main()

{

    scanf("%d%d%d%d", &x[0], &y[0], &x[1], &y[1]);

    r[0] = r[1] = 0;



    int N;

    scanf("%d", &N);

    N += 2;

    for (int i = 2; i < N; i++)

        scanf("%d%d%d", &x[i], &y[i], &r[i]);



    for (int i = 0; i < N; i++)

        for (int j = 0; j < N; j++)

            cost[i][j] = max(hypot(x[i] - x[j], y[i] - y[j]) - r[i] - r[j], 0.);



    fill(fixed, fixed + N, false);

    fill(d, d + N, numeric_limits<double>::infinity());

    d[0] = 0;

    while (true) {

        int v = -1;

        for (int i = 0; i < N; i++) {

            if (!fixed[i] && (v == -1 || d[i] < d[v]))

                v = i;

        }

        if (v == -1)

            break;

        fixed[v] = true;

        for (int i = 0; i < N; i++) {

            d[i] = min(d[i], d[v] + cost[v][i]);

        }

    }



    printf("%.12f\n", d[1]);

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <stdio.h>

#include <string.h>

#include <math.h>

#include <algorithm>

#include <vector>

using namespace std;



const int N = 1010;



struct node

{

	int x,y,r;

} a[N];



struct edge

{

	int v;

	double cost;

	edge(int x,double b):v(x),cost(b){};

};

int n;

double d[N];

bool vis[N];



vector<edge> G[N];



double cal(int i,int j)

{

	double sum = a[i].r + a[j].r;

	double xx = 1.0 * (a[i].x - a[j].x) * (a[i].x - a[j].x);

	double yy = 1.0 * (a[i].y - a[j].y) * (a[i].y - a[j].y);

	double ans = sqrt(xx+yy);

	if (sum >= ans) return 0;

	else return ans - sum;

}



void dij(void)

{

	for (int i = 0;i <= n + 1;i++) d[i] = 1e30;

	d[0] = 0;

	for (int i = 0;i <= n;i++)

	{

		double mi = 1e30;

		int x;

		for (int j = 0;j <= n + 1;j++)

		{

			if (!vis[j] && d[j] < mi)

			{

				mi = d[j];

				x = j;

			}

		}

		if (mi == 1e30) break;

		vis[x] = 1;

		for (auto e : G[x])

		{

			double cost = e.cost;

			int v = e.v;

			if (d[v] > cost + d[x])

			{

				d[v] = cost + d[x];

			}

		}

	}

}



int main()

{

	scanf("%d%d",&a[0].x,&a[0].y);

	a[0].r = 0;

	int x,y;

	scanf("%d%d",&x,&y);

	scanf("%d",&n);

	a[n+1].x = x,a[n+1].y = y,a[n+1].r = 0;

	for (int i = 1;i <= n;i++) scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].r);

	for (int i = 0;i <= n + 1;i++)

	{

		for (int j = i + 1;j <= n + 1;j++)

		{

			double len = cal(i,j);

			G[i].push_back(edge(j,len));

			G[j].push_back(edge(i,len));

		}

	}

	dij();

	printf("%.15f\n",d[n+1]);

	return 0;

}

// Optimized solution to the same problem (faster):
/*Lucky_Glass*/

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

using namespace std;

const int MAXN=1000;

const double INF=1e18;

int beg[2],ove[2],rnd[MAXN+5][3];

double dis[MAXN+5][MAXN+5];

int n;

double F[MAXN+5];

bool vis[MAXN+5];

double Dij()

{

	fill(F,F+MAXN+5,INF);

	F[0]=0;

	for(int i=0;i<=n;i++)

	{

		double MIN=INF;

		int u;

		for(int j=0;j<=n+1;j++)

			if(F[j]<MIN && !vis[j])

				MIN=F[j],u=j;

		vis[u]=true;

		for(int j=0;j<=n+1;j++)

			F[j]=min(F[j],F[u]+dis[u][j]);

	}

	return F[n+1];

}

int main()

{

	scanf("%d%d%d%d",&beg[0],&beg[1],&ove[0],&ove[1]);

	scanf("%d",&n);

	for(int i=1;i<=n;i++)

		for(int j=0;j<3;j++)

			scanf("%d",&rnd[i][j]);

	rnd[0][0]=beg[0];rnd[0][1]=beg[1];

	rnd[n+1][0]=ove[0];rnd[n+1][1]=ove[1];

	for(int i=0;i<=n+1;i++)

		for(int j=i+1;j<=n+1;j++)

			dis[i][j]=dis[j][i]=max(sqrt(1.0*(rnd[i][0]-rnd[j][0])*(rnd[i][0]-rnd[j][0])+1.0*(rnd[i][1]-rnd[j][1])*(rnd[i][1]-rnd[j][1]))-rnd[i][2]-rnd[j][2],0.0);

	printf("%.9lf\n",Dij());

	return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<cstdio>

#include<cmath>

#include<queue>

#include<vector>

#include<cstring>

#include<algorithm>

#define maxn 1005

using namespace std;

int xs,ys,xt,yt,n,x[maxn],y[maxn],r[maxn];

double dist[maxn],g[maxn][maxn];

queue<int> q;

bool inq[maxn];

int main()

{

	scanf("%d%d%d%d%d",&xs,&ys,&xt,&yt,&n);

	x[0]=xs,y[0]=ys,x[n+1]=xt,y[n+1]=yt;

	for(int i=1;i<=n;i++) scanf("%d%d%d",&x[i],&y[i],&r[i]);

	for(int i=0;i<=n+1;i++)

		for(int j=0;j<=n+1;j++)

			g[i][j]=max(0.0,sqrt(1.0*(x[i]-x[j])*(x[i]-x[j])+1.0*(y[i]-y[j])*(y[i]-y[j]))-r[i]-r[j]);

	for(int i=1;i<=n+1;i++) dist[i]=1e16;

	q.push(0); inq[0]=true;

	while(!q.empty())

	{

		int u=q.front(); q.pop();

		inq[u]=false;

		for(int v=0;v<=n+1;v++)

			if(dist[v]>dist[u]+g[u][v])

			{

				dist[v]=dist[u]+g[u][v];

				if(!inq[v]) { inq[v]=true; q.push(v); }

			}

	}

	printf("%.10f\n",dist[n+1]);

}

// Optimized solution to the same problem (faster):
/*Lucky_Glass*/

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

using namespace std;

const int MAXN=1000;

const double INF=1e18;

int beg[2],ove[2],rnd[MAXN+5][3];

double dis[MAXN+5][MAXN+5];

int n;

double F[MAXN+5];

bool vis[MAXN+5];

double Dij()

{

	fill(F,F+MAXN+5,INF);

	F[0]=0;

	for(int i=0;i<=n;i++)

	{

		double MIN=INF;

		int u;

		for(int j=0;j<=n+1;j++)

			if(F[j]<MIN && !vis[j])

				MIN=F[j],u=j;

		vis[u]=true;

		for(int j=0;j<=n+1;j++)

			F[j]=min(F[j],F[u]+dis[u][j]);

	}

	return F[n+1];

}

int main()

{

	scanf("%d%d%d%d",&beg[0],&beg[1],&ove[0],&ove[1]);

	scanf("%d",&n);

	for(int i=1;i<=n;i++)

		for(int j=0;j<3;j++)

			scanf("%d",&rnd[i][j]);

	rnd[0][0]=beg[0];rnd[0][1]=beg[1];

	rnd[n+1][0]=ove[0];rnd[n+1][1]=ove[1];

	for(int i=0;i<=n+1;i++)

		for(int j=i+1;j<=n+1;j++)

			dis[i][j]=dis[j][i]=max(sqrt(1.0*(rnd[i][0]-rnd[j][0])*(rnd[i][0]-rnd[j][0])+1.0*(rnd[i][1]-rnd[j][1])*(rnd[i][1]-rnd[j][1]))-rnd[i][2]-rnd[j][2],0.0);

	printf("%.9lf\n",Dij());

	return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <algorithm>

#include <iostream>

#include <iomanip>

#include <cstring>

#include <string>

#include <vector>

#include <queue>

#include <cmath>

using namespace std;



const int MAXN = 1000 + 10;



#define y1 MyY1

#define y2 MyY2

struct barrier

{

    int x, y, r;

};



int N;

int x1, x2, y1, y2;

vector <barrier> vbar;

double dist[MAXN];

bool inQueue[MAXN];



double precalcDist[MAXN][MAXN];

double getDist(int from, int to)

{

    double deltaX = vbar[from].x - vbar[to].x;

    double deltaY = vbar[from].y - vbar[to].y;

    return max(sqrt(deltaX * deltaX + deltaY * deltaY) - vbar[from].r - vbar[to].r, 0.0);

}



void SPFA()

{

    fill(dist, dist + N + 2, 1e100);

    memset(inQueue, 0x00, sizeof inQueue);



    queue <int> q;

    q.push(0);

    dist[0] = 0, inQueue[0] = true;



    while(!q.empty())

    {

        int to = q.front();

        inQueue[to] = false;

        q.pop();



        for(int i = 0; i <= N + 1; i++)

        {

            if(i == to)

                continue;



            if(dist[i] > dist[to] + precalcDist[i][to])

            {

                dist[i] = dist[to] + precalcDist[i][to];

                if(!inQueue[i])

                {

                    inQueue[i] = true;

                    q.push(i);

                }

            }

        }

    }

}



int main()

{

    ios::sync_with_stdio(false);

    cin.tie(0);



    int u, v, w;



    cin >> x1 >> y1 >> x2 >> y2 ;

    vbar.push_back(barrier{x1, y1, 0});

    vbar.push_back(barrier{x2, y2, 0});



    cin >> N ;

    for(int i = 1; i <= N; i++)

        cin >> u >> v >> w, vbar.push_back(barrier{u, v, w});



    for(int i = 0; i <= N + 1; i++)

        for(int j = 0; j < i; j++)

            precalcDist[i][j] = precalcDist[j][i] = getDist(i, j);



    SPFA();



    cout << fixed << setprecision(10) << dist[1] << endl ;



    return 0;

}


// Optimized solution to the same problem (faster):
#include<cstdio>

#include<cmath>

#include<cstring>

#include<algorithm>

using namespace std;

double f[1005][1005],dis[1005],a[1005][3];

bool b[1005];

int main()

{

	int i,j,k,n;

	double xi,xs,ys,xt,yt;

	scanf("%lf%lf%lf%lf",&xs,&ys,&xt,&yt);

	scanf("%d",&n);

	a[0][0]=xs;a[0][1]=ys;a[0][2]=0;

	a[n+1][0]=xt;a[n+1][1]=yt;a[n+1][2]=0;

	for(i=1;i<=n;i++)

		scanf("%lf%lf%lf",&a[i][0],&a[i][1],&a[i][2]);

	n++;

	for(i=0;i<=n;i++)

		for(j=i+1;j<=n;j++){

			f[i][j]=f[j][i]=sqrt((a[i][0]-a[j][0])*(a[i][0]-a[j][0])+(a[i][1]-a[j][1])*(a[i][1]-a[j][1]))-(a[i][2]+a[j][2]);

			if(f[i][j]<0)

				f[j][i]=f[i][j]=0;

		}

	for(i=0;i<=1003;i++) dis[i]=1e18;

	dis[0]=0; 

	for(i=0;i<n;i++){ 

		xi=1e18;

		k=0; 

		for(j=0;j<=n;j++){

            if(b[j]==0&&dis[j]<xi){ 

				xi=dis[j]; 

				k=j; 

			} 

        }

		b[k]=1; 

		for(j=0;j<=n;j++)

			dis[j]=min(dis[j],dis[k]+f[k][j]);

	}

	printf("%.9lf",dis[n]);

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>

#define F(i,a,b) for(int i=(a);i<=(b);++i)

#define F2(i,a,b) for(int i=(a);i<(b);++i)

#define dF(i,a,b) for(int i=(a);i>=(b);--i)

#define dF2(i,a,b) for(int i=(a);i>(b);--i)

#define dF3(i,a,b) for(int i=(a)-1;i>=(b);--i)

using namespace std;



long double tx,ty;

int n;

long double x[1005],y[1005],r[1005];

bool vis[1005];

long double dis[1005];



long double d(int p,int q){return max((long double)0,sqrt((x[p]-x[q])*(x[p]-x[q])+(y[p]-y[q])*(y[p]-y[q]))-r[p]-r[q]);}



int main(){

	cin>>x[0]>>y[0]>>tx>>ty;

	scanf("%d",&n); x[n+1]=tx, y[n+1]=ty;

	F(i,1,n) cin>>x[i]>>y[i]>>r[i];

	F(i,1,n+2) dis[i]=1e20;

	int now=0; vis[0]=1;

	F(k,1,n+2){

		F(i,1,n+1) dis[i]=min(dis[i],dis[now]+d(now,i));

		int nxt=n+2;

		F(i,1,n+1) if(!vis[i]&&dis[nxt]>dis[i]) nxt=i;

		vis[nxt]=1;

		now=nxt;

	}

	printf("%.15lf",(double)dis[n+1]);

	return 0;

}

// Optimized solution to the same problem (faster):
#include <cstdio>

#include <cstring>

#include <cmath>

#include <algorithm>

const int MAXN = 1005;

const double eps = 1e-12;





int xs, ys, xt, yt, n;

struct node

{

	int x, y, z;

}p[MAXN];

double f[MAXN][MAXN], dis[MAXN];



double dist(int x, int y, int u, int v)

{

	return sqrt(1.0 * (1ll * (x-u) * (x-u) + 1ll * (y-v) * (y-v)));

}



double calc(int i, int j)

{

	double d = dist(p[i].x, p[i].y, p[j].x, p[j].y);

	if(p[i].z + p[j].z - d < eps) return d - p[i].z - p[j].z;

	return 0;

}



bool vis[MAXN];



int main ()

{

	scanf("%d%d%d%d", &xs, &ys, &xt, &yt);

	scanf("%d", &n); n++;

	for(int i = 1; i < n; i++)

		scanf("%d%d%d", &p[i].x, &p[i].y, &p[i].z);

	p[0].x = xs, p[0].y = ys, p[0].z = 0;

	p[n].x = xt, p[n].y = yt, p[n].z = 0;

	for(int i = 0; i <= n; i++)

		for(int j = i; j <= n; j++)

			f[i][j] = f[j][i] = calc(i, j);

	memset(dis, 127, sizeof dis); dis[0] = 0;

	for(int i = 1; i <= n; i++)

	{

		int k = -1;

		for(int j = 0; j <= n; j++)

			if(!vis[j] && (k == -1 || dis[j] - dis[k] < eps))

				k = j;

		if(k < 0) break;

		vis[k] = 1;

		for(int j = 0; j <= n; j++)

			if(!vis[j] && dis[k] + f[k][j] - dis[j] < eps)

				dis[j] = dis[k] + f[k][j];

	}

	printf("%.10lf\n", dis[n]);

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#define max(a,b) (a>b?a:b)

using namespace std;

double d[1010],map[1010][1010];

double x[1010],y[1010],r[1010];

bool v[1010];

double tx,ty;

int n;

int main(){

    cin>>x[0]>>y[0]>>tx>>ty>>n;

    x[n+1]=tx,y[n+1]=ty;

    for(int i=1;i<=n;i++) cin>>x[i]>>y[i]>>r[i];

    for(int i=0;i<=n+1;i++)

        for(int j=0;j<=n+1;j++){

            if(i==j) continue;

            double ls=(sqrt((double) (x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]))-(r[i]+r[j]));

            map[i][j]=max(ls,0);

        }

    for(int i=1;i<=n+1;i++) d[i]=(double) 1e10;

    int now=0;

    double mini;

    while(!v[now]){

        v[now]=true;

        for(int i=0;i<=n+1;i++){

            if(now==i) continue;

            if(!v[i]&&d[now]+map[now][i]<d[i])

                d[i]=d[now]+map[now][i];

        }

        mini=(double) 1e10;

        for(int i=0;i<=n+1;i++)

            if(!v[i]&&d[i]<mini) now=i,mini=d[i];

    }

    printf("%.10lf\n",d[n+1]);

    return 0;

}

// Optimized solution to the same problem (faster):
#include <cstdio>

#include <cstring>

#include <cmath>

#include <algorithm>

const int MAXN = 1005;

const double eps = 1e-12;





int xs, ys, xt, yt, n;

struct node

{

	int x, y, z;

}p[MAXN];

double f[MAXN][MAXN], dis[MAXN];



double dist(int x, int y, int u, int v)

{

	return sqrt(1.0 * (1ll * (x-u) * (x-u) + 1ll * (y-v) * (y-v)));

}



double calc(int i, int j)

{

	double d = dist(p[i].x, p[i].y, p[j].x, p[j].y);

	if(p[i].z + p[j].z - d < eps) return d - p[i].z - p[j].z;

	return 0;

}



bool vis[MAXN];



int main ()

{

	scanf("%d%d%d%d", &xs, &ys, &xt, &yt);

	scanf("%d", &n); n++;

	for(int i = 1; i < n; i++)

		scanf("%d%d%d", &p[i].x, &p[i].y, &p[i].z);

	p[0].x = xs, p[0].y = ys, p[0].z = 0;

	p[n].x = xt, p[n].y = yt, p[n].z = 0;

	for(int i = 0; i <= n; i++)

		for(int j = i; j <= n; j++)

			f[i][j] = f[j][i] = calc(i, j);

	memset(dis, 127, sizeof dis); dis[0] = 0;

	for(int i = 1; i <= n; i++)

	{

		int k = -1;

		for(int j = 0; j <= n; j++)

			if(!vis[j] && (k == -1 || dis[j] - dis[k] < eps))

				k = j;

		if(k < 0) break;

		vis[k] = 1;

		for(int j = 0; j <= n; j++)

			if(!vis[j] && dis[k] + f[k][j] - dis[j] < eps)

				dis[j] = dis[k] + f[k][j];

	}

	printf("%.10lf\n", dis[n]);

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

#include<queue>

#define SF scanf

#define PF printf

#define MAXN 1010

using namespace std;

typedef long long ll;

double stx,sty,edx,edy;

int n;

struct node{

	double x,y,r;	

}p[MAXN];

double lenp(double x,double y,double xx,double yy){

	return sqrt((x-xx)*(x-xx)+(y-yy)*(y-yy));

}

double len(int x,int y){

	double distx=lenp(p[x].x,p[x].y,p[y].x,p[y].y);

	return max(0.0,distx-p[x].r-p[y].r);

}

double len1[MAXN][MAXN];

double dist[MAXN];

int inq[MAXN];

queue<int> q;

void spfa(){

	while(!q.empty()){

		int x=q.front();

		inq[x]=0;

		q.pop();

		for(int i=1;i<=n;i++){

			if(i==x)

				continue;

			if(dist[i]<0||dist[i]>dist[x]+len1[x][i]){

				dist[i]=dist[x]+len(x,i);

				if(inq[i]==0){

					inq[i]=1;

					q.push(i);	

				}

			}

		}

	}

}	

int main(){

	SF("%lf%lf%lf%lf",&stx,&sty,&edx,&edy);

	SF("%d",&n);

	for(int i=1;i<=n;i++)

		SF("%lf%lf%lf",&p[i].x,&p[i].y,&p[i].r);

	p[++n].x=stx;

	p[n].y=sty;

	p[n].r=0;

	p[++n].x=edx;

	p[n].y=edy;

	p[n].r=0;

	for(int i=1;i<=n;i++)

		for(int j=1;j<=n;j++)

			len1[i][j]=len(i,j);

	for(int i=1;i<=n;i++)

		dist[i]=-1;

		

	dist[n]=0;

	q.push(n);

	spfa();

	PF("%.10lf\n",dist[n-1]);

}

	

// Optimized solution to the same problem (faster):
#include <cstdio>

#include <cstring>

#include <cmath>

#include <algorithm>

const int MAXN = 1005;

const double eps = 1e-12;





int xs, ys, xt, yt, n;

struct node

{

	int x, y, z;

}p[MAXN];

double f[MAXN][MAXN], dis[MAXN];



double dist(int x, int y, int u, int v)

{

	return sqrt(1.0 * (1ll * (x-u) * (x-u) + 1ll * (y-v) * (y-v)));

}



double calc(int i, int j)

{

	double d = dist(p[i].x, p[i].y, p[j].x, p[j].y);

	if(p[i].z + p[j].z - d < eps) return d - p[i].z - p[j].z;

	return 0;

}



bool vis[MAXN];



int main ()

{

	scanf("%d%d%d%d", &xs, &ys, &xt, &yt);

	scanf("%d", &n); n++;

	for(int i = 1; i < n; i++)

		scanf("%d%d%d", &p[i].x, &p[i].y, &p[i].z);

	p[0].x = xs, p[0].y = ys, p[0].z = 0;

	p[n].x = xt, p[n].y = yt, p[n].z = 0;

	for(int i = 0; i <= n; i++)

		for(int j = i; j <= n; j++)

			f[i][j] = f[j][i] = calc(i, j);

	memset(dis, 127, sizeof dis); dis[0] = 0;

	for(int i = 1; i <= n; i++)

	{

		int k = -1;

		for(int j = 0; j <= n; j++)

			if(!vis[j] && (k == -1 || dis[j] - dis[k] < eps))

				k = j;

		if(k < 0) break;

		vis[k] = 1;

		for(int j = 0; j <= n; j++)

			if(!vis[j] && dis[k] + f[k][j] - dis[j] < eps)

				dis[j] = dis[k] + f[k][j];

	}

	printf("%.10lf\n", dis[n]);

}

// Fastest known solution for this problem: