3101: 小澳的葫芦

小澳最喜欢的歌曲就是《葫芦娃》。
一日表演唱歌,他尽了洪荒之力,唱响心中圣歌。
随之,小澳进入了葫芦世界。
葫芦世界有 n 个葫芦,标号为 1~ n。n 个葫芦由 m 条藤连接,每条藤连接了
两个葫芦,这些藤构成了一张有向无环图。小澳爬过每条藤都会消耗一定的能量。
小澳站在 1 号葫芦上(你可以认为葫芦非常大,可以承受小澳的体重),他
想沿着藤爬到 n 号葫芦上,其中每个葫芦只经过一次。
小澳找到一条路径,使得消耗的能量与经过的葫芦数的比值最小。

输入文件第一行两个正整数 n,m,分别表示葫芦的个数和藤数。 接下来 m 行,每行三个正整数 u,v,w,描述一条藤,表示这条藤由 u 连向 v, 小澳爬过这条藤需要消耗 w 点能量。

一行一个实数,表示答案(误差不超过 10^-3)。

4 6
1 2 1
2 4 6
1 3 2
3 4 4
2 3 3
1 4 8

2.000