A6040 | 「2017 山东一轮集训 Day7」重排

给定一个 $ n $ 个点 $ m $ 条边的边带权的 S-DAG，一个 S-DAG 即在一个有向无环图的基础上,可能会有若干的重边与自环。

你现在想从 $ s $ 点走到 $ t $ 点，当你每走到一个点 $ u $ 时，$ u $ 连出去的边的边权会等概率地随机排列，多次走到同一个点的话这个点的边权就会随机多次。一开始在 $ s $ 的时候也是会这样的。

你想尽快到达终点，因此想知道最小的期望距离是多少？

边权等概率地随机排列的意思是：设 $ u $ 有 $ k $ 条出边，其指向的点为 $ v_1, v_2, \ldots, v_k $，边权为 $ c_1, c_2, \ldots, c_k $，那么边权会等概率地变成 $ c_1, c_2, \ldots, c_k $ 的全排列的一种。总共有 $ k! $ 种全排列。

当你走到点 $ u $ 时，其权值重新排列出的形状你是可以马上知道的，所以你可以根据新的权值来决策你的行动。

假如不可能到达则输出 $ -1 $。

第一行四个整数 $ n, m, s, t $。
接下来 $ m $ 行，每行三个数 $ u_i, v_i, c_i $，其中 $ u_i $ 与 $ v_i $ 为整数，$ c_i $ 可能为浮点数。表示图中有一条从 $ u_i $ 出发到 $ v_i $ 的长度为 $ c_i $ 的边。

输出一行一个浮点数，代表最小的期望距离，假如不可能到达输出 $ −1 $。当你的答案与标准答案的绝对误差不超过 $ 10 ^ {-6} $ 时会被视为正确。