Consider a weighted directed graph $G=(V,E)$ and a weight function $w:E\to \mathbb{R}$, where the weight of each edge $e=(i,j)$ ($i\ne j, i\in V, j\in V$) is defined as $w_{i,j}$. Let $n=|V|$. A sequence $c=(c_1,c_2,\dots,c_k)$ ($c_i\in V$) is a cycle in $G$ if and only if $(c_i,c_{i+1})$ for $1\le i < k$ and $(c_k,c_1)$ are all in $E$. In this case, $k$ is called the length of the cycle $c$. Let $c_{k+1}=c_1$, and define the average value of the cycle $c=(c_1,c_2,\dots,c_k)$ as:

$$\mu(c)=\sum_{i=1}^{k} w_{c_i,c_{i+1}}/k$$

This is the average of the weights of all edges in $c$. Let $\mu^*(c)=\min\{\mu(c)\}$ be the minimum average value among all cycles $c$ in $G$. Given a graph $G=(V,E)$ and a weight function $w:E\to \mathbb{R}$, your goal is to find the minimum average value $\mu^*(c)=\min\{\mu(c)\}$ of all cycles in $G$.

Input

The first line contains two integers $n$ and $m$, separated by a space, where $n=|V|$ and $m=|E|$ represent the number of vertices and edges in the graph, respectively. Each of the following $m$ lines contains three space-separated numbers $i, j$, and $w_{i,j}$, representing an edge $(i,j)$ with weight $w_{i,j}$. The input guarantees that the graph $G=(V,E)$ is connected, contains at least one cycle, and there exists a vertex from which all other vertices are reachable.

Output

Output a single real number $\mu^*(c)=\min\{\mu(c)\}$, formatted to 8 decimal places.

Examples

Input 1

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

Output 1

3.66666667

Input 2

2 2
1 2 -2.9
2 1 -3.1

Output 2

-3.00000000

Note

In Example 1, there are two cycles: $(1,2,3)$ and $(1,2,4)$. The average value of the first cycle is 5, and the average value of the second cycle is $11/3$. In Example 2, there is a negative cycle.

Constraints

• 20% of the data: $n\le 100, m\le 1000$
• 50% of the data: $n\le 1000, m\le 5000$
• 100% of the data: $n\le 3000, m\le 10000$
• 100% of the data: $|w_{i,j}|\le 10^7$