题目描述

给定一个 $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}$ 时会被视为正确。

4 4 1 3
1 2 1
2 3 6
2 4 3
1 1 3

6.50000

数据范围与提示

对于 $20\%$ 的数据，$n, m \leq 100$，每个点的出边数量不超过 $5$；
对于 $40\%$ 的数据，$n, m \leq 200$；
另外有 $20\%$ 的数据，给出的图中不存在自环；
对于 $100\%$ 的数据，$ 1 \leq n, m \leq 1000; s \neq t; 0 \leq c_i \leq 100 $，$c_i$ 的位数不超过 $8$ 位。图中可能存在重边与自环。