Car的旅行路线

有S座城市，每座城市的四个机场恰好构成一个非退化矩形。给出每座城市任意三个机场的整数坐标，顺序任意。同一城市的任意两个机场之间均有直达高速铁路，费用为欧氏距离乘该城市费率T_i；不同城市的任意两个机场之间均有直达航线，费用为欧氏距离乘统一航空费率t。可以任意换乘。

从城市A任意机场出发，到城市B任意机场结束，求最小总费用。允许A=B，此时答案为0。

输入格式

第一行整数Q，0<=Q<=10。每组第一行S t A B，1<=S<=100，1<=t<=10000，1<=A,B<=S。接下来S行，每行x1 y1 x2 y2 x3 y3 T_i。三个点互不相同，保证恰为某个非退化矩形的三个顶点；补出的第四顶点也满足坐标范围。全部四顶点坐标为1..10000的整数，1<=T_i<=10000。不同城市的机场允许重合。

输出格式

每组一行非负费用，固定保留两位小数。与标准答案保留两位小数后的数值相差不超过0.01即接受。Q=0时无输出。

输入样例

1
3 10 1 3
1 1 1 3 3 1 30
2 5 7 4 5 2 1
8 6 8 8 11 6 3

输出样例

47.55