ストーリー

日本の $47$ 都道府県を道路で繋ごう。

問題文

地域 $1$ から地域 $N$ までの $N$ 個の地域があります。初めこれらの地域間には道路は存在しません。

binapくんは（ $6$ 面）サイコロと $M$ 組の $3$ つ組整数 $(U_1, V_1, C_1), \cdots, (U_M, V_M, C_M)$ が書かれたリストを用いて、全ての地域が道路を通って互いに行き来できるようになるまで以下の一連の操作を繰り返します。

• サイコロを振る。

• binapくんは出目を確認してから $1$ 以上 $M$ 以下の整数 $i$ を選ぶ。

• 出目が $C_i$ 以上であれば地域 $U_i$ と地域 $V_i$ を双方向に結ぶ道路が作られる。

binapくんは操作回数の期待値を最小にするのが目的です。最適に行動し続けた場合の操作回数の期待値を求めてください。本題の制約下で期待値は有限であることが示せます。

制約

• $2\leq N \leq 47$

• $\displaystyle N-1\leq M \leq \frac{N(N-1)}{2}$

• $1 \leq U_i < V_i \leq N$ $(1\leq i \leq M)$

• $(U_i,V_i) \neq (U_j,V_j)$ $( i \neq j )$

• $1\leq C_i \leq 6$ $(1\leq i \leq M)$

• $i = 1,2,\cdots, M$ なる整数 $i$ 全てについて地域 $U_i$ と地域 $V_i$ 間に道路を作った場合、全ての地域を互いに行き来できる。

• 入力は全て整数。

入力

$N$ $M$
$U_1$ $V_1$ $C_1$
$\vdots$
$U_M$ $V_M$ $C_M$

出力

binapくんが最適に行動した場合の操作回数の期待値を $1$ 行で出力してください。想定解との絶対誤差または相対誤差が $10^{−6}$ 以下のとき正解と判定されます。

サンプル

3 3
1 2 1
1 3 2
2 3 3

2.03333333333333

2 1
1 2 1

1

1.000000

5 6
2 4 5
4 5 4
1 2 6
1 4 4
2 5 4
3 4 2

6.2592