题目描述

Rupert 是英格兰某个小镇上唯一的房产经纪人。他每卖出一栋房屋，都会收取成交金额的 $5\%$ 作为佣金。

Rupert 每年组织一次大型拍卖。镇上的每个家庭编号为 $1$ 到 $n$，都必须参加这次拍卖，不过是否出价、是否接受报价都是可选的。每个家庭会对自己想搬入的房屋出价，前提是他们能够同时卖掉目前居住的房屋。

整个过程非常透明：如果 Rupert 代表卖方接受了恰当的买方报价，他可以准确知道自己能获得多少佣金。为了提高总佣金，他可以舍弃部分买方报价。事实上，如果这样能够赚得更多，他甚至可以舍弃某个家庭的全部报价，让该家庭继续住在原来的房屋中。

请你求出：当 Rupert 以最优方式舍弃报价时，他能够获得的最大佣金。

输入格式

输入包含：

• 第一行包含两个整数 $n,m$（$1\le n\le 150$，$0\le m\le n(n-1)$），分别表示参与市场的家庭数量和报价数量。
• 接下来 $m$ 行描述所有报价。
  • 第 $i$ 行包含三个整数 $f_i,h_i,a_i$（$1\le f_i,h_i\le n$，$f_i\ne h_i$，$0\le a_i\le 10^6$）。
  • $f_i$ 表示提出报价的家庭，$h_i$ 表示目标房屋当前所属的家庭，$a_i$ 表示报价金额。
  • 同一个家庭不会对同一栋房屋提出超过一次报价。

输出格式

输出 Rupert 在最优舍弃报价后能够获得的佣金。

答案的绝对误差或相对误差不得超过 $10^{-6}$。

样例 1

输入：
4 5
1 2 3
2 3 9
3 1 5
3 2 11
4 1 6

输出：
1.0

样例 2

输入：
4 5
1 2 15
2 3 9
3 1 5
3 2 11
4 1 6

输出：
1.45