1 //Awsm.Definer →_→
2 //E-Mail: willywu1998@foxmail.com
3 #include <cstdio>
4 #include <deque>
5 #include <cmath>
6 #include <memory.h>
7 #include <iostream>
8 #define MAX 0x3f3f3f3f
9 #define mod(x) ( sqrt((x) * (x)) )
10 using namespace std;
11 struct v { //vector(location)
12 int x,y;
13 v (){};v(int a,int b):x(a),y(b){};
14 v operator +(const v& b) {return v(x+b.x,y+b.y);}
15 v operator -(const v& b) {return v(x-b.x,y-b.y);}
16 int operator * (const v& b) {return x*b.x + y*b.y;}
17 };
18 inline v get4(v &p1,v &p2,v &p3) {
19 if((p2 - p1) * (p3 - p1) == 0) return p2 - p1 + p3;
20 if((p1 - p2) * (p3 - p2) == 0) return p1 - p2 + p3;
21 return p1 - p3 + p2;
22 }
23 inline void getv(v &k) {
24 scanf("%d%d",&k.x,&k.y);
25 }
26 int n,s,t,A,B; //the meaning of s will be changed in function "work"...
27 double dis[404][404]={0};
28 inline void makegragh() { //build dis[][]
29 v p[404];
30 int Ti;
31 for(int i=1;i<=s;i+=4) {
32 getv(p[i]),getv(p[i+1]),getv(p[i+2]);scanf("%d",&Ti);
33 p[i+3]=get4(p[i],p[i+1],p[i+2]);
34 for(int j=0;j<3;++j)for(int k=j;k<4;++k)
35 dis[i+j][i+k]=dis[i+k][i+j]=Ti * mod((p[i+k]-p[i+j]));
36 for(int j=1;j<i;++j)for(int k=0;k<4;++k)
37 dis[j][i+k]=dis[i+k][j]=t * mod((p[i+k]-p[j]));
38 }
39 }
40 inline double SPFA() {
41 deque <int> Q;
42 int k = 4 * A - 3,K = 4 * B - 3;
43 Q.push_front(k),Q.push_front(k+1),Q.push_front(k+2),Q.push_front(k+3);
44 bool in_Q[404] = {0};in_Q[k]=in_Q[k+1]=in_Q[k+2]=in_Q[k+3]=1;
45 double cost[404];
46 int i,t;
47 for(i=1;i<=s;++i) cost[i] = MAX;
48 cost[k]=cost[k+1]=cost[k+2]=cost[k+3]=0;
49 while(!Q.empty()) {
50 t = Q.front(); Q.pop_front(); in_Q[t] = 0;
51 for(i = 1;i <= s;++i) {
52 if(i==t)continue;
53 if(cost[i] > cost[t] + dis[i][t]) { //relax
54 cost[i] = cost[t] + dis[i][t];
55 if(in_Q[i])continue;
56 if(Q.empty() || cost[Q.front()] < cost[i])Q.push_back(i);
57 else Q.push_front(i);
58 in_Q[i] = 1;
59 }
60 }
61 }
62 return min(min(cost[K],cost[K+1]),min(cost[K+2],cost[K+3]));
63 }
64 void work() {
65 scanf("%d%d%d%d",&s,&t,&A,&B);s *= 4;//s -> sum of airports
66 makegragh();
67 printf("%.1f\n", SPFA()); //(0) -> (4*n+1)
68 }
69 int main(){
70 #ifdef DEBUG
71 freopen("test.in","r",stdin);
72 #endif
73 scanf("%d",&n);
74 while(n--)
75 work();
76 return 0;
77 }
