题目描述

有 $n$ 个人，其中一些人的银行账户之间可以互相转账。每次转账都会从转账金额中扣除一定比例的手续费。给定每对可转账账户之间的手续费比例，求 $A$ 最少需要准备多少钱，才能通过一次或多次转账，使 $B$ 最终收到 $100$ 元。

输入格式

第一行两个整数 $n,m$。

接下来 $m$ 行，每行三个整数 $x,y,z$，表示 $x$ 与 $y$ 之间互相转账时扣除 $z\%$ 的手续费。

最后一行两个整数 $A,B$。保证 $A$ 可以直接或间接向 $B$ 转账。

输出格式

输出最少需要准备的金额，保留小数点后八位。

样例

3 3
1 2 1
2 3 2
1 3 3
1 3

103.07153164

数据范围

$2\le n\le2000$，$1\le m\le200000$，$1\le x,y,A,B\le n$，$x\ne y$，$1\le z<100$。保证最优金额不超过 $10^{12}$。