U419115 售货机

**时间限制：** 1.0 秒 **空间限制：** 512 MB **提交前的提示：** 如果想使用 `C++` 输出指定位数的小数，可以使用 `stdio.h` 库或者 `iostream` 以及 `iomanip` 库。例：将浮点数 $x$ 保留三位小数输出可以使用 `printf("%.3f", x)` 或者 `std::cout

清华大学的自动售货机一共有 $n$ 种饮料出售，每种饮料有自己的售价，并在售货机上各有一个出售口。购买第 $i$ 种饮料时，可以在第 $i$ 个出售口支付 $a_i$ 的价格，售货机便会在下方的出货处放出对应的饮料。 又到了清凉的夏日，自动售货机为每种饮料各进货了 **$1$ 瓶**存储在其中，供同学购买。但是，自动售货机却出现了一些故障，它有可能会出货不属于这个出售口的饮料。 对于第 $i$ 个出售口，**支付 $a_i$ 的价格购买后**，如果饮料 $i$ 与饮料 $b_i$ 都有存货，有 $p_i$ 的概率出货饮料 $i$，有 $1-p_i$ 的概率出货饮料 $b_i$。如果其中一个有存货，另一个已经没有存货，则将出货有存货的那一种饮料。如果两种饮料都没有存货，售货机将不会出货任何饮料并发出警报。**即便最后你没有获得任何饮料，也需要支付 $a_i$ 的价格**。 长颈鹿下楼来到这台售货机前，希望能买到最近火爆全网的饮料 $x$，此时售货机中 $n$ 种饮料都存货有 $1$ 瓶。由于它知道售货机有问题，因此决定采取这样的策略来购买： - 在 $n$ 个出售口中等概率选择一个出售口 $s$ 开始购买，支付这个出售口的价格 $a_s$ 并得到出货。 - 当得到想要的饮料 $x$ 时，停止购买流程，满意欢喜地离去。 - 当得到不想要的饮料 $y$ 时，继续在第 $y$ 个支付口购买，支付 $a_y$ 的价格并等待出货。 - 当售货机发出警报时，停止购买流程，灰心丧气地离去。 现在他希望你告诉他，他这一次购买流程期望支付的价钱数量是多少？

从标准输入读入数据。 第一行两个正整数 $n,x$。 接下来 $n$ 行每行两个整数与一个浮点数，其中第 $i$ 行表示 $a_i,b_i,p_i$。

输出到标准输出。 一行一个实数表示答案，表示长颈鹿按他的策略买水期望支付的价钱。 记答案为 $a$，而你的输出为 $b$，那么当且仅当 $|a-b|

### 样例 1 解释 售货机里饮料 $1$ 与饮料 $2$ 各有一瓶，且当两瓶都还有存货时，在第 $1$ 个出售口有 $0.1$ 的概率买到饮料 $2$，在第 $2$ 个出售口有 $0.6$ 的概率买到饮料 $1$。 - 长颈鹿有 $0.5$ 的概率初始选择第 $1$ 个出售口开始购买，并支付 $8$ 元。 - 有 $0.1$ 的概率直接出货饮料 $2$，一共支付 $8$ 元，这种情况的概率是 $0.05$。 - 有 $0.9$ 的概率出货饮料 $1$，则长颈鹿会再支付 $8$ 元重新从第 $1$ 个出售口购买饮料。由于饮料 $1$ 已售空，第二次购买时必定直接出货饮料 $2$，一共支付 $16$ 元，这种情况的概率是 $0.45$。 - 长颈鹿有 $0.5$ 的概率初始选择第 $2$ 个出售口开始购买，并支付 $7$ 元。 - 有 $0.4$ 的概率直接出货饮料 $2$，一共支付 $7$ 元，这种情况的概率是 $0.2$。 - 有 $0.6$ 的概率出货饮料 $1$，则长颈鹿会再支付 $8$ 元重新从第 $1$ 个出售口购买饮料。由于饮料 $1$ 已售空，第二次购买时必定直接出货饮料 $2$，一共支付 $15$ 元，这种情况的概率是 $0.3$。 于是期望支付的价钱为 $8\times 0.05+16\times 0.45+7\times 0.2+15\times 0.3=13.5$。 ### 子任务 对于所有数据，保证 $n\le 2000,~ 1\le b_i,x\le n,~ b_i\ne i,~ 0\le a_i\le 100~ , 0\le p_i\le 1$，且 $p_i$ 不超过两位小数。 **本题采用捆绑测试，你只有通过一个子任务中的所有测试点才能得到该子任务的分数。** - 子任务 1（50 分）：保证 $n\le 10$。 - 子任务 2（30 分）：保证 $p_i = 0$。 - 子任务 3（20 分）：无特殊限制。