试题描述

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

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

输入数据

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

接下来m行，每行包含三个整数a，b，p ( 1<=p<=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<=1000，m<=3000

100%的数据，n<=10000，m<=30000