J. Jagged Roads
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Henrique Holanda (not to be confused with the ICPC world finalist Davi Holanda) loves running and has been training a lot for a physical evaluation, known as the Training Assessment on Fatiguing (something like that, I can't seem to remember), commonly called TAF. The TAF is divided into two parts; first, he needs to run from one point in the city to another and then do as many pushups as possible. For some reason, the organizers of this event have forgotten how to use a stopwatch and so the time it takes to complete the first part doesn't really matter.

Because of this, Henrique Holanda scouts how the first part is going to happen and finds out that there are $$$n$$$ possible crossroads he can go through in order to get to the finish line; he begins running at crossroad $$$1$$$ and finishes at crossroad $$$n$$$. Besides this, there are $$$m$$$ roads that arbitrarily connect two different crossroads, and since he wants to finish the running section as least fatigued as possible, instead of assigning a distance to it, he assigns a tiredness factor to it.

He measures his tiredness factor the following way: when he begins running, his current tiredness factor is $$$1$$$. When he goes through a road to go from one crossroad to another, he multiplies his own tiredness factor by the value associated with that road. Can you help him find out what's the minimum tiredness factor he's able to end the running section with? Since the answer can get really big, he wants the logarithm base seven of the answer.

Input

The first line contains two integers, $$$n$$$, $$$m$$$, $$$(1 \leq n \leq 10^5)$$$, $$$(n - 1 \leq m \leq \min(3 \times 10^5, \frac{n \times (n - 1)}{2}))$$$ — the number of crossroads and the number of roads.

Each of the next $$$m$$$ lines will contain the description of a road. Each line contains three integers, $$$u_i$$$, $$$v_i$$$, $$$c_i$$$, $$$(1 \leq u_i, v_i, \leq n, u_i \neq v_i)$$$, $$$(1 \leq c_i \leq 10^9)$$$ — a road connecting crossroads $$$u_i$$$ and $$$v_i$$$ that multiplies his tiredness factor by $$$c_i$$$.

Output

For each test case, output a real number — the logarithm base seven of the tiredness factor. That being, if Henrique Holanda's tiredness factor is $$$k$$$, you should print $$$log_7(k)$$$. Your answer will be considered correct if its absolute or relative error does not exceed $$$10^{-6}$$$, that being if your answer is $$$a$$$ and the jury's is $$$b$$$, then the judge will check if $$$\frac{|a - b|}{max(1, b)} \leq 10^{-6}$$$.

Example
Input
5 7
1 2 4
2 3 6
1 3 5
4 5 8
4 2 3
3 5 7
2 5 16
Output
1.827087475346916