考虑一个带权无向图 $G(V, E; w)$。一个割是将顶点划分为两个非空子集 $S$ 和 $\overline{S}$ 的划分。我们定义割 $\{S, \overline{S}\}$ 的苗条度（slimness）为 $$\frac{\max_{(u,v)\in E,\, u\in S,\, v\in \overline{S}} w(u, v)}{\min(|S|, |\overline{S}|)}.$$

换句话说，割的苗条度是跨越该割的所有边中的最大边权，除以较小部分的顶点数。例如，下图中的割通过选择 $S = \{0, 1, 3\}$ 和 $\overline{S} = \{2, 4, 5\}$（或反之），其苗条度为 $\max(4, 1, 2)/3 = 4/3$。

在所有可能的割中，哪一个是苗条度最小的？请你求出其最小的苗条度。

输入格式

第一行包含两个整数 $n$ 和 $m$，分别表示图中的顶点数和边数（$2 \le n \le 14\,000$，$1 \le m \le 30\,000$）。顶点的编号从 $0$ 到 $n - 1$。

接下来的 $m$ 行，每行包含三个由空格隔开的整数 $x_i, y_i, w_i$，表示一条连接顶点 $x_i$ 和 $y_i$ 且权重为 $w_i$ 的边（$0 \le x_i, y_i < n$，$1 \le w_i \le 10^8$）。保证图是连通的，且不包含自环或重边。

输出格式

输出一个浮点数，表示图中苗条度最小的割的苗条度。如果你的答案与标准答案的绝对误差或相对误差在 $10^{-8}$ 以内，则被视为正确。

样例

输入格式 1

6 7
0 1 3
1 2 4
0 3 1
1 4 1
2 5 5
3 4 2
4 5 4

输出格式 1

1.33333333333

在样例中，割 $S = \{0, 1, 3\}$ 和 $\overline{S} = \{2, 4, 5\}$ 的苗条度为 $4/3$。