某片神秘大陆有 \(n\) 个岛屿和 \(m\) 座变化的桥，岛屿编号 $1\sim n$ 。

这些变化的桥都是单行道，第 \(i\) 座桥只能从岛屿 \(u_i\) 去岛屿 \(v_i\) 。每座桥桥每分钟都可能会发生变化，第 \(i\) 座桥每分钟有 \(p_i\) 的概率畅通，有 $1-p_i$ 的概率堵塞。当桥畅通时可以用 $1$ 分钟时间通过这座桥，当桥堵塞时则无法使用这座桥。每一分钟每座桥是否畅通都是独立的，既不依赖上一分钟的状态，也和当前其他的桥毫无关联。

一个探险者想要从岛屿 $1$ 去岛屿 \(n\) ，却被这些变化的桥搞得很头疼。比如说，当探险者走到岛屿 \(u_i\) 正准备经过第 \(i\) 条边去往岛屿 \(v_i\) ，但这座桥却暂时处于堵塞状态，则探险者可以另外选一条座从岛屿 \(u_i\) 到其他岛屿的畅通的桥，也可以选择在岛屿 \(u_i\) 上等待 $1$ 分钟。虽然探险者并不确定 $1$ 分钟后这座桥是否畅通，但探险者精通概率论，每一秒都会选择期望最优的方式。

现在，探险者想知道自己从岛屿 $1$ 走到岛屿 \(n\) 花费时间的期望值。

第一行两个整数 \(n,m\) ，表示岛屿数量和桥的数量。

接下来 \(m\) 行，每行三个整数 \(u_i,v_i,1000\times p_i\) ，表示第 \(i\) 座桥的起点、终点、畅通概率的 $1000$ 倍。

输出一行一个实数表示期望时间。你可以输出任意多少位小数，如果你的答案与标准答案的绝对误差或相对误差不超过 $10^{-6}$ 就会被判定为正确答案。

样例2解释

探险者一开始在岛屿 $1$ ，按照如下策略前往岛屿 $3$ ：

• 如果桥 $1\to3$ 畅通，如果畅通了就走这座桥；
• 如果桥 $1\to 3$ 堵塞但桥 $1\to2$ 畅通，就先走桥 $1\to 2$ ，然后在岛屿 $2$ 等待桥 $2\to3$ 的桥畅通；
• 如果桥 $1\to 3$ 和桥 $1\to2$ 都堵塞，就在岛屿 $1$ 等一分钟。

可以计算出，这个策略的期望用时为 $1.75$ 分钟。

样例2解释

只要一直等待到 $1\to2$ 的桥畅通即可。

数据范围

对于100%的数据：
$2\leq n\leq 10^5$
$1\leq m\leq 3\times 10^5$
$1\leq u_i,v_i\leq n$
$0\leq 1000\times p_i\leq 1000$
保证没有重边和自环
保证一定有畅通概率 \(>0\) 的路线可以从岛屿 $1$ 走到岛屿 \(n\)
正确答案不超过 $10^6$ 。

性质A：每条边 \(v_i=u_i+1\) 。

性质B：每条边 \(u_i<v_i\) 。

性质C：除了第 $1$ 条边，其他每条边 \(v_i=u_i+1\) 。