Zag 在新冠疫情隔离期间正在玩一个有趣的游戏。游戏有 $n$ 个不同的事件，玩家从事件 1 开始。

除了结束事件（编号为 $n$）外，每个事件都有若干个后续事件。当处于某个特定事件时，你可以以给定的概率晋级到它的某一个后续事件。如果你成功晋级到其中一个后续事件，你将无法返回。如果你不幸未能晋级，你可以尝试转移到其他后续事件。如果你尝试了所有的后续事件但仍然失败，游戏结束。

Zag 让游戏开发者 Coffee 告诉他所有的事件及其后续事件，以及成功晋级的概率，以便你可以帮助他确定到达结束事件的最大概率。

输入格式

第一行包含两个整数 $n, m$（$2 \le n \le 5 \times 10^4$，$1 \le m \le 10^5$），分别表示事件的数量和后续关系的条数。

接下来的 $m$ 行，每行包含三个整数 $x, y, p$（$1 \le x, y \le n$，$0 \le p \le 100$），表示你可以以 $p\%$ 的概率从事件 $x$ 晋级到事件 $y$。

保证你无法通过后续关系返回到已经经历过的事件。

输出格式

输出一个实数，表示到达结束事件的最大概率。当你的答案与标准答案的绝对误差或相对误差不超过 $10^{-6}$ 时，将被视为正确。

样例

输入样例 1

4 4
1 2 50
1 3 50
2 4 30
3 4 70

输出样例 1

0.425000