I. Infinity Money Glitch
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Tiago was playing the famous Directed Bank game with his friends Leonardo, Gabriel, and Paulo.

As everyone knows, the Directed Bank board has $$$N$$$ positions and $$$M$$$ possible moves, with the $$$i$$$-th move represented by the tuple $$$(U_i, V_i, W_i)$$$; that is, if the player is on position $$$U_i$$$, they can move to position $$$V_i$$$, adding $$$W_i$$$ to their balance. It's possible for the balance to become negative during the game.

The game always starts from position number 1, and in a round, the player can make a valid move or wait on the same spot, without losing or gaining anything.

Being an expert Directed Bank player, Tiago soon discovers a bug feature in the game! It's possible to accumulate infinite money! But it's not so clear how this could happen, and Leonardo and Gabriel disagreed with the statement, demanding proof. Tiago said he would demonstrate with an example of infinite moves during the game, which would also take an infinitely long time.

But since the pizza they ordered was almost arriving, there was only enough time for Tiago to play a finite number of rounds, and the problem remained open.

Knowing that you are a great programmer and that you are training for the UFPE Programming Contest, Paulo proposed you a challenge: prove or disprove Tiago!

But since infinity is a very long time, you only need to simulate $$$10^{998244353}$$$ rounds to convince the group of friends. That is, given the description of the board, state the largest possible average value per round that can be obtained on this board after $$$10^{998244353}$$$ rounds.

Input

The first line of input contains two integers $$$2 \le N \le 2000$$$, $$$1 \le M \le 2000$$$, representing the number of positions on the board and the number of possible valid moves.

The following $$$M$$$ lines contain three integers $$$U_i, V_i, W_i$$$, with $$$1 \le U_i, V_i \le N$$$ and $$$-10^9 \le W_i \le 10^9$$$, where $$$U_i \neq V_i$$$. This represents the list of valid moves.

Note that multiple edges between the same pair of positions are allowed.

Output

Print a real number, the answer to the problem. Your solution will be considered correct if it has a relative or absolute error less than or equal to $$$10^{-6}$$$.

Examples
Input
2 2
1 2 2
2 1 -1
Output
0.5
Input
3 3
1 2 -5
2 3 5
3 1 -5
Output
0
Note

In sample 1, a valid strategy is to go from square 1 to square 2, return to square 1, then go to square 2, and so on $$$(1, 2, 1, 2, 1, 2, \ldots)$$$. After infinite rounds, the average points accumulated per round will be $$$0.5$$$.

In sample 2, a valid strategy is to never leave the first square, thus never losing points in the balance.