题目描述

受不了 Farmer John 的长期残暴统治，奶牛 Bessie 终于决定要逃跑了。

John 有 N 个农场，编号为 1 ~ N。有 M 条双向通行的道路，每条道路连接两个不同的农场，两个不同的农场间最多有一条道路。

为了防止奶牛逃跑，John 在每条道路上都安装了监控。

Bessie 正在农场 1，逃离 Farmer John 统治的出口在农场 N。只要能够到达农场 N，那么她就成功逃脱了。

现在，Bessie 已经计算出了途经每条道路时被发现的概率。她想知道选择怎样的逃跑路线可以使得自己逃脱的概率最大。

你能帮助她吗？你只需要输出她逃脱的最大概率，保留 3 位小数。

输入格式

第一行包含两个整数 $N, M$

接下来 $M$ 行每行包含三个整数 $u,v,w$，表示农场 $u$ 和 $v$ 之间有一条双向道路，经过这条道路被发现的概率为 $w$%。

输出格式

输出一个实数，表示 Bessie 逃脱的最大概率，保留 3 位小数。

样例输入

5 7
5 2 0
3 5 20
2 3 30
2 1 50
3 4 20
4 1 15
3 1 30

样例输出

0.560

数据范围

50% 的数据：$2 ≤ N ≤ 100, 1 ≤ M <= N×(N-1)/2, 1 ≤ u, v ≤ N, u ≠ v, 0 ≤ w ≤ 100$

100% 的数据：$2 ≤ N ≤ 5000, 1 ≤ M <= N×(N-1)/2, 1 ≤ u, v ≤ N, u ≠ v, 0 ≤ w ≤ 100$