415. [HAOI 2009]旅行

【题目描述】

小明住在城市 $1$，而他的朋友小芳住在城市 $n$。最近小明收到小芳的邀请，准备于近期赴约。可是由于最近下了很多暴雨，很多道路都被淹没。从城市 $1$ 出发到城市 $n$ 之间有很多小城镇，并且两个小城镇之间有一条直接道路相连。小明经过对近期天气和地形的科学分析，绘出了每条道路能顺利通行的概率。

为了能顺利到达目的地，请帮助小明找出一条最稳妥的路线，也就是从城市 $1$ 出发到达城市 $n$ 的路线中能顺利通行的最大概率。

【输入格式】

文件第一行包含两个整数 $n$ 和 $m$，$n$ 为城市数，$m$ 为道路条数。

接下来 $m$ 行，每行包含三个整数 $a$，$b$，$p ( 1 \leq p \leq 100 )$，表示小城镇 $a$ 与小城镇 $b$ 间有一条道路，顺利通过这条道路的概率为 $p\%$。

【输出格式】

一个实数 $P$，为到达城市 $n$ 的最大概率，$P$ 精确到小数点后 $6$ 位。

【样例输入】

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

【样例输出】

61.200000

【样例说明】

选择路线为 $1-4-3-5$，概率为 $85\%*90\%*80\%=61.2\%$

【数据规模与约定】

$30\%$ 的数据，$n \leq 1000，m \leq 3000$；

$100\%$ 的数据，$n \leq 10000，m \leq 30000$。