Problem1117--吝啬的PIPI

1117: 吝啬的PIPI

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 449  Solved: 202
[Submit] [Status] [Web Board] [Creator:]

Description

PIPI想转钱给 POPO, 但是不同的银行之间的转账是要收取一定的手续费的,而且只有特定的银行之间才可以互相进行转账,给定这些银行之间转账时需要从转账金额里扣除的手续费百分比,请问PIPI最少需要多少钱使得转账后POPO收到100元。

Input

输入包含多组测试用例。

对于每组测试用例,第一行输入两个正整数n,m,分别表示总银行数和可以互相转账的银行的对数。(0<n<=2000

以下m行每行输入三个整数x,y,z。表示标号为x银行和标号为y银行之间互相转账需要扣除z%的手续费(z<100)。

最后一行两个整数,分别表示PIPI和POPO的编号

Output

对于每组测试用例,输出PIPIPOPO到账100元最少需要的费用。精确到小数点后8位。如果不能够转给POPO,输出"Impossible"。

Sample Input

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

Sample Output

103.07153164

Source/Category

中等