Problem H
Slim Cut

Consider a weighted, undirected graph $G(V,E;w)$. A cut is a partition of the vertices into two non-empty subsets $S$ and $\overline S$. Let us define the slimness of the cut $\{ S, \overline S\} $ to be

In other words, the sliminess of the cut is the maximum weight among all edges crossng the cut, divided by size of the smaller part. For example, the cut below has slimness $\max (4, 1, 2) / 3 = 4/3$, by choosing $S = \{ 0, 1, 3\} $ and $\overline S = \{ 2, 4, 5\} $ (or the other way round).

Among all possible cuts, which one is the slimmest (i.e. has the minimum slimness)? You are asked to find its slimness.

Note: Time limit is strict. Your implementation must be efficient.

Input

The first line contains two integers $n$ and $m$, representing the number of vertices and the number of edges in the graph ($2 \leq n \leq 14\, 000$, $1 \leq m \leq 30\, 000$). The vertices are labelled from $0$ to $n-1$. The next $m$ lines each contains three space-separated integers $x_ i, y_ i, w_ i$, representing an edge connecting vertices $x_ i$ and $y_ i$ of weight $w_ i$ ($0 \leq x_ i, y_ i < n$, $1 \leq w_ i \leq 10^8$).

The graph is guaranteed to be connected. It has no self loops or multiple edges.

Output

Output a floating point number representing the slimness of the slimmest cut of the graph. Any answer with an absolute or relative error within $10^{-8}$ will be accepted.

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

1.33333333333