题目描述

徐老师最近喜欢上玩一个 爬塔游戏，在这个游戏中共有 $n$ 个 塔 编号分别为 $1 \sim n$,而且每座塔都有自己的坐标 $(x_i,y_i)$

塔和塔之间存在一些双向路径，允许玩家从第座塔 $i$ 移动到第 $j$ 座塔。

如果第 $i$ 座塔和第 $j$ 座塔之间存在路径，那么这条路径的长度即为 $\sqrt{(x_i -x_j)^2+(y_i -y_j)^2}$

玩家的移动速度是 $v$，他通过一条长度为 $dis$ 的路径需要花费的时间为 $dis / v$

而游戏允许玩家进行跳跃的操作，允许玩家从第 $i$ 个塔垂直向下跳跃到另一个塔，也就是说对于两座塔 $i,j$，如果 $x_i = x_j$ 且 $y_i > y_j$ 则允许玩家从第 $i$ 座塔跳跃到第 $j$ 座塔（允许过程中穿过其他路径和塔），所花费的时间满足自由落体公式：$\sqrt{(y_i - y_j) * 2 / g}$，这里的 $g$ 取 $10$

现在徐老师需要从 $1$ 号塔移动到 $n$ 号塔，他最少需要花费多少时间？

输入格式

输入第一行包含两个整数 $n,v$ 表示有 $n$ 座塔，玩家的移动速度是 $v$

接下来 $n$ 行，每行包含三个整数 $x_i,y_i,u_i$，分别表示第 $i$ 个点的坐标是 $(x_i,y_i)$ ，以及第 $i$ 座塔和第 $u_i$ 座塔之间存在路径，若 $u_i = 0$ 则表示这条边不存在

输出格式

输出仅包含一行，表示徐老师需要从 $1$ 号塔移动到 $n$ 号塔最少需要花费的时间（保留两位小数）

数据范围

对于 $40\%$ 的数据，$1 \leq n \leq 10, 1 \leq v \leq 10, 0 \leq x_i,y_i \leq 100$

对于 $100\%$ 的数据，$1 \leq n \leq 100, 1 \leq v \leq 10, 0 \leq x_i,y_i \leq 100$

样例输入

9 1
5 0 0
5 5 1
6 5 2
7 6 2
6 9 2
3 6 2
4 5 2
3 2 7
7 2 3

样例输出

8.13