题目描述

在电影《蓝调兄弟》中，$Elwood$和$Jack$长大的孤儿院将被教育局收购，除非他们能在芝加哥库克县评估办公室缴纳$5000$美元税款。当他们通过演出赚到这笔钱后，需要设法前往芝加哥。但这并不容易，因为他们被警察、乡村乐队和纳粹分子追捕，而且距离芝加哥有$106$英里，天色已暗他们还戴着墨镜。

作为"上帝的任务"，你需要帮助他们找到前往芝加哥的最安全路线。本题中，最安全路线是指不被抓概率最大的路径。

输入格式

• 多个测试用例
• 每个用例首行两个整数：
  • $n$：交叉路口数量$（2 ≤ n ≤ 100）$
  • $m$：街道数量$（1 ≤ m ≤ n(n-1)/2）$
• 接下来$m$行描述街道：
  • 每行3个整数$a b p$：路口$a$到$b$的双向街道，成功通过概率$p$
• 输入以$0$结束

输出格式

对每个测试用例：

• 计算从路口$1$（皇宫酒店）到路口$n$（芝加哥广场）的最大成功概率
• 输出百分比，精确到$6$位小数
• 格式示例：$61.200000 percent$

输入样例 1：

5 7
5 2 100
3 5 80
2 3 70
2 1 50
3 4 90
4 1 85
3 1 70
0

输出样例 1：

61.200000 percent

题目来源

2005 年乌尔姆本地音乐节